Problemi 049

Kërkesa

Në një varg S me shkronja, gjejmë një nënvarg që formon fjalën CHEF dhe i heqim këto shkronja. Gjeni sa herë mund ta bëjmë këtë veprim.

Referenca: https://www.codechef.com/problems/CHRL2

Shembull

$ cat input.txt
2
CHEFCHEFFFF
CHHHEEEFFCC

$ python3 prog.py < input.txt
2
1

Zgjidhja 1

W = 'CHEF'
for _ in range(int(input())):
    S = list(input())
    total_cnt = 0
    while True:
        cnt = 0
        i = 0
        j = 0
        while i < len(S):
            if S[i] == W[j]:
                S[i] = 'X'
                j += 1
                if j == 4:
                    cnt += 1
                    j = 0
            i += 1
        total_cnt += cnt
        if cnt == 0:
            break
    print(total_cnt)

Sqarime

Me indeksin i marrim me radhë shkronjat në vargun e dhënë. Me indeksin j shënojmë shkronjat në CHEF. Shkronjat që përputhen i ndryshojmë në X që mos ti kontrollojmë prapë herën tjetër. Kur gjejmë shkronja korresponduese për të katra shkronjat e CHEF (d.m.th kur j bëhet 4) rrisim numrin e fjalëve të gjetura (cnt) me 1 dhe e kthejmë indeksin j në fillim. Këtë punë e përsërisim deri sa të mos gjenden më fjalë të tilla në vargun e dhënë (cnt == 0).

Zgjidhja 2

for _ in range(int(input())):
    S = input()
    c = ch = che = chef = 0
    for l in S:
        if l == 'C':
            c += 1
        elif l == 'H':
            if c > 0:
                c -= 1
                ch += 1
        elif l == 'E':
            if ch > 0:
                ch -= 1
                che += 1
        elif l == 'F':
            if che > 0:
                che -= 1
                chef += 1
    print(chef)

Sqarime

Te ndryshorja c ruajmë numrin e shkronjave C që kemi gjetur deri në një moment të caktuar, por që nuk mund të lidhen me një H nga mbrapa. Te ndryshorja ch mbajmë numrin e nënvargjeve CH që kemi gjetur, por që nuk mund të formojnë nënvargun CHE. E njëjta gjë edhe për ndryshoret che dhe chef.

Nqs në këtë moment shikojmë p.sh. një E në varg, atere kjo mund të lidhet me një nga nënvargjet CH që kemi numëruar deri tani dhe të krijojë një nënvarg CHE, kështu që pakësojmë me 1 ndryshoren ch dhe shtojmë me 1 ndryshoren che. Por kjo mund të bëhet nqs kemi parë të paktën një nënvarg CH deri tani.

Në përfundim, te ndryshorja chef do kemi numrin e gjithë nënvargjeve CHEF të mundshëm.

Zgjidhja 3

for _ in range(int(input())):
    S = input()
    c = ch = che = chef = 0
    for l in S:
        if l == 'C':
            c += 1
        elif l == 'H':
            if c > ch:
                ch += 1
        elif l == 'E':
            if ch > che:
                che += 1
        elif l == 'F':
            if che > chef:
                chef += 1
    print(chef)

Sqarime

Llogjika është e ngjashme me zgjidhjen e dytë, vetëm se te ndryshorja ch (për shembull) mbajmë të gjitha nënvargjet e mundshme CH që kemi parë deri tani, që mund të jenë pjesë ose jo e nënvargjeve CHE ose CHEF. Nqs tani shohim një E dhe numri i të gjitha nënvargjeve CH që kemi parë deri tani është më i madh se numri i të gjitha nënvargjeve CHE, atere këtë shkronjë E mund ta lidhim me ndonjë nga nënvargjet CH që janë tepër dhe të krijojmë një nënvarg të ri CHE. Kështu që e rrisim me 1 ndryshoren che.

Shënim: Duhet vënë në dukje se zgjidhja e dytë dhe e tretë janë më të shpejta se zgjidhja e parë, sepse këto e gjejnë përgjigjen me një kontroll të vetëm në vargun e dhënë, kurse zgjidhja e parë duhet ta kontrollojë vargun disa herë, deri sa të mos gjejë më ndonjë nga nënvargjet e kërkuar. Këtë gjë mund ta verifikoni edhe duke i provuar këto zgjidhje këtu: https://www.codechef.com/submit/CHRL2 Zgjidhja e parë të jep vetëm 25 pikë, kurse 2 të tjerat të japin 100 pikë të plota.

Detyra

Gimi është i famshëm për dembelizmin e tij në shkollë. Ai i lë gjithmonë gjërat për në minutën e fundit. Tani ka N problema për të zgjidhur në një detyrë që duhet ta dorëzoj nesër, dhe siç mund ta merrni me mënd nuk ka zënë gjë me dorë.

Por ai ka një plan, si gjithmonë. Puna e parë, bleu një pako me RedBull. Pastaj do punojë pa pushim deri sa të zgjidhë gjysmat e problemave (nëse N është çift gjysma është N/2, përndryshe është (N+1)/2). Pastaj do pushojë për B minuta. Pastaj do vazhdojë me gjysmat e problemave që mbeten dhe do bëjë përsëri një pushim prej B minutash, e kështu me radhë deri sa ti mbarojë të gjitha problemat. Në fillim atij i duhen M minuta për të zgjidhur një problem, por pas çdo pushimi koha e zgjidhjes së një problemi dyfishohet.

Sa kohë i duhet Gimit deri sa të mbarojë edhe problemin e fundit?

Referenca: https://www.codechef.com/problems/TALAZY

Shembull

$ cat input.txt
2
9 1 2
123456 123456 123456

$ python3 prog.py < input.txt
45
131351258112

Në rastin e parë, janë 9 problema për tu zgjidhur, koha e pushimit është 1 minutë, dhe fillimisht i duhen 2 minuta për të zgjidhur një problemë. Fillimisht Gimi do zgjidhë 5 problemat e para, dhe për këto i duhen 5*2 = 10 minuta. Pastaj do bëjë 1 minutë pushim. Pastaj do zgjidhë 2 problemat e tjera, dhe për këto i duhen 2*4 = 8 minuta. Pastaj do bëjë prapë 1 minutë pushim. Pastaj do zgjidhë 1 problem për 8 minuta. Pastaj prapë 1 min pushim. Pastaj do zgjidhë problemin e fundit për 16 min. Gjithsej do ti duhen 10 + 1 + 8 + 1 + 8 + 1 + 16 = 45 minuta për ti përfunduar të gjitha problemat.