Problemi 054

Kërkesa

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.

Zgjidhja

for _ in range(int(input())):
    n, b, m = map(int, input().split())
    koha = 0
    while n > 0:
        if n % 2 == 0:
            p = n // 2
        else:
            p = (n + 1) // 2
        koha += p * m
        koha += b
        n -= p
        m *= 2
    koha -= b
    print(koha)

Detyra

Është një ditë feste dhe Cufi duhet të raportojë rreth parakalimeve që po bëhen në bulevard. Grupe të ndryshme njerëzish parakalojnë në formë autokolone, njëra pas tjetrës, ku dy autokolona mund të kenë edhe njëfarë distance nga njëra-tjetra. Sa herë që shikon fillimin e një autokolone Cufi shënon në një fletore një H, gjatë kohës që autokolona ecën ai vazhdon të shënojë pika (.), dhe kur shikon fundin e autokolonës shënon një T. Gjithashtu, për të shënuar distancat midis autokolonave ai përdor pika.

Meqenëse autokolonat kalojnë me radhë njëra pas tjetrës, një raport i saktë do ishte diçka e tillë: “..H..T…HTH….T.”, ose “…”, ose “HT”. Kurse “T…H..H.T”, “H..T..H” dhe “H..H..T..T” do ishin të pasakta.

Formalisht, një autokolonë paraqitet nga një H, që pasohet nga disa pika (ndoshta asnjë), dhe në fund ka një T. Një raport i saktë është ai që fillon me disa pika (ndoshta asnjë), vazhdon me disa (ndoshta zero) autokolona midis të cilave mund të ketë edhe pika, dhe mbaron me disa pika (ndoshta asnjë).

Cufi ka ndenjur vonë mbrëmë duke festuar dhe është pak përgjumësh, kështu që raporti i tij mund të jetë i pasaktë. Bëni një program që verifikon nëse raporti është i saktë ose jo.

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

Shembull

$ cat input.txt
6
18
..H..T...HTH....T.
3
...
10
H..H..T..T
2
HT
11
.T...H..H.T
7
H..T..H

$ python3 prog.py < input.txt
Valid
Valid
Invalid
Valid
Invalid
Invalid

“H..H..T..T” nuk është e saktë sepse kolona e dytë fillon para se të mbarojë e para.

“.T…H..H.T” nuk është i saktë sepse ka një fund kolone T pa pasur ndonjë fillim H.

“H..T..H” nuk është i saktë sepse ka një fillim kolone H që nuk ka fund T.