Problemi 067

Kërkesa

Cookie Clicker është një lojë e ndërtuar me JavaScript ku lojtarët klikojnë te figura e një biskote gjigande. Duke klikuar aty fitojnë biskota. Ata mund ti shpenzojnë këto biskota për të ndërtuar punishte. Këto punishte i ndihmojnë që të bëjnë edhe më shumë biskota.

Në këtë problemë ju filloni me 0 biskota. Ju fitoni 2 biskota çdo sekondë duke klikuar te biskota gjigande. Nqs keni të paktën C biskota ju mund të blini një punishte, e cila ju kushton C biskota, por ju ndihmon që të fitoni F biskota më tepër në çdo sekondë.

Kur të keni fituar X biskota (pa ato që keni shpenzuar për të blerë punishte) ju fitoni. Gjeni sa kohë do t’ju duhet për të fituar, duke përdorur strategjinë më të mirë të mundshme (dmth gjeni kohën më të shkurtër të mundshme për të fituar).

Referenca: https://code.google.com/codejam/contest/dashboard?c=2974486#s=p1

Shembull

$ cat input.txt
4
30.0 1.0 2.0
30.0 2.0 100.0
30.50000 3.14159 1999.19990
500.0 4.0 2000.0

$ python3 prog.py < input.txt
Case #1: 1.0000000
Case #2: 39.1666667
Case #3: 63.9680013
Case #4: 526.1904762

Jepen numrat C, F dhe X.

Në rastin e fundit, C=500, F=4 dhe X=2000. Strategjia më e mirë e mundshme do ishte kështu: 1. Ju filloni me 0 biskota, duke prodhuar 2 biskota në sekondë. 1. Pas 250 sekondash do keni C=500 biskota dhe mund të blini një punishte që prodhon F=4 biskota në sekondë. 1. Pasi të blini punishten ju do keni 0 biskota dhe mund të prodhoni 6 biskota në sek. 1. Punishtja tjetër do t’ju kushtojë 500 biskota dhe mund ta blini pas 83.3333333 sekondash. 1. Pasi ta keni blerë punishten e dytë do keni 0 biskota, por prodhimi i biskotave në sekondë shkon në 10. 1. Një punishte tjetër do t’ju kushtojë 500 biskota, të cilën mund ta blini pas 50 sekondash. 1. Pasi të blini punishten e tretë do keni 0 biskota, por mund të prodhoni 14 biskota në sekondë. 1. Për të blerë një punishte tjetër do t’ju duhen 500 biskota, por në fakt është më mirë që mos ta blini atë dhe të prisni deri sa të bëni X=2000 biskota, për të cilën ju duhen afërsisht 142.8571429 sekonda. 1. Koha totale për të fituar është: 250 + 83.3333333 + 50 + 142.8571429 = 526.1904762 sekonda.

Vini re që prodhimi i biskotave bëhet në mënyrë të vazhdueshme (dmth pas 0.1 sekondave të para të lojës ju do keni prodhuar 0.2 biskota).

Zgjidhja

for i in range(int(input())):
    c, f, x = map(float, input().split())
    time = 0.0                     # total time spent
    r = 2.0                        # rate of getting cookies
    while True:
        t1 = x/r                   # time to win without rate increase
        t2 = c/r + x/(r + f)       # time to win with a rate increase
        if t1 <= t2:               # no need to increase the rate again
            print("Case #{}: {}".format(i+1, time + t1))
            break
        else:                      # increase the rate once more
            time += c/r
            r += f

Sqarime

Sa kohë që nuk janë bërë akoma C biskota (që duhen për të blerë një punishte) ne vetëm mund të vazhdojmë prodhimin, se nuk kemi ç’të bëjmë tjetër. Kur të kemi C biskota duhet të vendosim nëse është më mirë të blejmë një punishte tjetër apo të vazhdojmë prodhimin me këto punishte që kemi. Këtë vendim e marrim duke llogaritur kohën që duhet për të fituar pa punishte tjetër dhe kohën që duhet për të fituar duke blerë një punishte tjetër, dhe duke parë se cila prej tyre është më e shkurtër.

Detyra

Në një rrugë të drejtë dhe të ngushtë po lëvizin disa makina, të cilat kanë shpejtësi maksimale të ndryshme. Nqs rrugën përpara do ta kishin bosh, makinat do preferonin që të ecnin me shpejtësinë e tyre maksimale. Por nqs kanë përpara një makinë më të ngadaltë, makinat janë të detyruara ta ulin shpejtësinë, meqenëse nuk mund të parakalojnë, dhe të ecin njëra-pas-tjetrës vargan.

Bëni një program që merr shpejtësitë e makinave dhe gjen se sa prej tyre po ecin me shpejtësi maksimale. Mund të supozojmë se rruga është shumë e gjatë dhe makinat kanë qenë duke ecur në të për një kohë të gjatë.

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

Shembull

$ cat input.txt
3
1
10
3
8 3 6
5
4 5 1 2 3

$ python3 prog.py < input.txt
1
2
2

Makinat po lëvizin nga e djathta në të majtë.

Në rastin e dytë, makina me shpejtësi 6 ndodhet pas asaj me shpejtësi 3, kështu që nuk mund të ecë me shpejtësi maksimale.

Në rastin e tretë, makina me shpejtësi 5 ndodhet pas asaj me shpejtësi 4, kështu që nuk mund të ecë me shpejtësi maksimale. Po ashtu, makinat 2 dhe 3 ndodhen pas asaj me shpejtësi 1, kështu janë futur në vargan. Me shpejtësinë e tyre maksimale ecin vetëm makinat 4 dhe 1.