Problemi 089

Kërkesa

Fituesit të një olimpiade programimi i takon të marrë si shpërblim një çek me vlerën N. Mirëpo të paktën një nga shifrat e numrit N është 4, ndërkohë që tastiera e makinës që shkruan çekun e ka të prishur tastin me numrin 4. Megjithatë organizatorët e gjetën zgjidhjen duke shkruar dy çeqe, shuma e të cilëve është N, dhe asnjëri prej të cilëve nuk e përmban shifrën 4. Gjeni dy numra të tillë.

Referenca: https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/0000000000088231

Shembull

$ cat input.txt
3
4
940
4444

$ python3 prog.py < input.txt
Case #1: 2 2
Case #2: 852 88
Case #3: 667 3777

Zgjidhja

for t in range(int(input())):
    n = input()
    n1 = []
    n2 = []
    for d in n:
        if d == '4':
            n1.append('3')
            n2.append('1')
        else:
            n1.append(d)
            n2.append('0')
    a = ''.join(n1)
    b = ''.join(n2)
    print('Case #{}: {} {}'.format(t+1, a, b))

Sqarime

Kur krijojmë dy numrat, për çdo shifër të ndryshme nga 4 e vendosim këtë shifër te numri i parë, ndërkohë që te i dyti vendosim 0, kurse për çdo shifër të barabartë me 4 vendosim shifrën 3 te numri i parë dhe shifrën 1 tek i dyti. Në këtë mënyrë garantojmë që shuma e tyre të jetë sa numri i dhënë, dhe asnjë prej tyre të mos përmbajë shifrën 4.

Detyra

Sot keni një agjendë të ngjeshur, plot me gjëra të rëndësishme. Jeni lodhur goxha për tu pregatitur dhe për tu siguruar që veprimtaritë nuk kanë mbivendosje me njëra-tjetrën. Tani është mëngjes dhe po filloni të merakoseni se pavarësisht nga entuziazmi dhe dëshira e mirë, ndoshta nuk do të keni energji të mjaftueshme për ti bërë të gjitha me përkushtim të plotë.

Duhet ti përdorni energjitë tuaja me kujdes. Ditën e filloni plot me energji - E xhaul (joules) për të qenë më të saktë. Niveli juaj i energjisë asnjëherë nuk mund të bjerë më poshtë se 0 (përndryshe do të binit i pafuqishëm), dhe po ashtu nuk mund të rritet më shumë se E. Për secilën nga veprimtaritë mund të shpenzoni një sasi jo-negative energjie (ndoshta zero), dhe pas çdo veprimtarie do rifitoni R xhaul energji, por gjithmonë pa e kaluar nivelin maksimal të energjisë prej E xhaul (energjia e tepërt thjesht shkon dëm).

Disa prej veprimtarive janë më të rëndësishme se të tjerat. Për secilën veprimtari i keni një vlerë \(v_i\) që shpreh rëndësinë e kësaj veprimtarie për ju. Përfitimi që keni nga secila veprimtari është vlera e kësaj veprimtarie, shumëzuar me sasinë e energjisë që shpenzoni për të. Sa është përfitimi më i madh total që mund të keni?

Radha e veprimtarive në kalendar nuk mund të ndryshohet, duhet ta përdorni energjinë sa më mirë të jetë e mundur me atë kalendar që keni.

Referenca: https://code.google.com/codejam/contest/2418487/dashboard#s=p1&a=1

Shembull

$ cat input.txt
3
5 2 2
2 1
5 2 2
1 2
3 3 4
4 1 3 5

$ python3 prog.py < input.txt
Case #1: 12
Case #2: 12
Case #3: 39

Në rreshtin e parë kemi numrat E, R dhe N. Në rreshtin pasardhës kemi N vlerat \(v_i\) për secilën prej N veprimtarive, sipas radhës.

Në rastin e parë, mund ti shpenzojmë të 5-ta xhaulët për veprimtarinë e parë, pas asaj do rifitojmë 2 xhaul, të cilat mund ti shpenzojmë për veprimtarinë e dytë. Kështu që përfitimi do jetë 52 + 21 = 12.

Në rastin e dytë mund të shpenzojmë 2 xhaul për veprimtarinë e parë, i rifitojmë ato, dhe shpenzojmë 5 xhaul për veprimtarinë e dytë. Përfitimi: 21 + 52 = 12.

Në rastin e tretë, rifitimi i energjisë është i barabartë me energjinë maksimale, që do të thotë se pas çdo veprimtarie i rifitojmë plotësisht të gjitha energjitë e harxhuara. Kështu që mund të shpenzojmë plot 3 xhaul për secilën veprimtari. Përfitimi total: 34 + 31 + 33 +35 = 39.