Problemi 093

Kërkesa

Një robot alien po kërcënon gjithësinë, me një rreze që mund të shkatërrojë gjithë njohurinë mbi algoritmet. Duhet ta ndalojmë!

Për fat, e dimë se si punon roboti. Duke filluar me një rreze me fuqi 1, ai zbaton njëri pas tjetrit udhëzimet në një program, nga e majta në të djathtë. Çdo udhëzim është një nga këto: - C (charge): Dyfisho fuqinë e rrezes. - S (shoot): Godit me rreze, duke shkaktuar një dëm të barabartë me fuqinë e rrezes.

P.sh. nëse programi është SCCSSC, roboti do bëjë këto: - Godit, duke shkaktuar 1 dëm. - Dyfisho, fuqia bëhet 2. - Dyfisho, fuqia bëhet 4. - Godit, dëmi 4. - Godit, dëmi 4. - Dyfisho, fuqia bëhet 8.

Në këtë rast dëmi total është: 1 + 4 + 4 = 9.

Algoritmistat më të mirë të gjithësisë kanë krijuar një mbështjellë mbrojtëse e cila mund të përballojë një dëm total deri në D. Mirëpo programi i robotit mund të shkaktojë dëm edhe më shumë se kaq.

Presidenti i Gjithësisë ka dalë vullnetar që të shkojë në hapësirë dhe të hakojë programin e robotit para se ai ta zbatojë atë. Mënyra e vetme se si mund ta hakojë (pa e kuptuar roboti) është duke u ndërruar vendin dy udhëzimeve fqinje. P.sh. programin e mësipërm mund ta ndryshojë duke u shkëmbyer vendet udhëzimeve 3 dhe 4, duke e bërë programin SCSCSC. Kjo do ta pakësonte dëmin total në 7. Pastaj mund ta ndryshonte prapë duke e bërë SCSSCC dhe duke e pakësuar dëmin total në 5, e kështu me radhë.

Që roboti mos të dyshojë, presidenti duhet të bëjë sa më pak hakime. Cili është numri më i vogël i hakimeve që janë të nevojshme për të siguruar që dëmi total që shkakton programi nuk e kalon vlerën D, nëse kjo është e mundur?

Referenca: https://codejam.withgoogle.com/2018/challenges/00000000000000cb/dashboard

Shembull

$ cat input.txt
6
1 CS
2 CS
1 SS
6 SCCSSC
2 CC
3 CSCSS

$ python3 prog.py < input.txt
Case #1: 1
Case #2: 0
Case #3: IMPOSSIBLE
Case #4: 2
Case #5: 0
Case #6: 5

Jepet numri D dhe programi P.

Zgjidhja

def total_damage(P):
    damage = 0
    strength = 1
    for c in P:
        if c == 'S': damage += strength
        if c == 'C': strength += strength
    return damage

for t in range(int(input())):
    D, P = input().split()
    D = int(D)
    P = list(P)
    
    hacks = 0
    damage = total_damage(P)
    while True:
        if damage <= D:
            ans = hacks
            break
        
        # make a hack
        for i in range(len(P)-1, 0, -1):
            if P[i]=='S' and P[i-1]=='C':
                P[i] = 'C'
                P[i-1] = 'S'
                hacks += 1
                break
            
        new_damage = total_damage(P)
        if new_damage == damage:
            ans = 'IMPOSSIBLE'
            break
        else:  # new_damage < damage
            damage = new_damage
        
    print('Case #{}: {}'.format(t+1, ans))

Sqarime

Meqenëse duam të bëjmë sa më pak hakime, atere duhet të fillojmë ti bëjmë këto nga fundi i programit, sepse aty kanë efektin më të madh. Sa herë që bëjmë një hakim llogarisim përsëri dëmin total. Nëse ky është bërë <= D, atere kemi mbaruar punë, nuk është nevoja të vazhdojmë me hakime. Nëse është i barabartë me dëmin e mëparshëm, kjo do të thotë që nuk kemi arritur të bëjmë asnjë hakim dhe nuk është e mundur ta ulim akoma më tepër dëmin, kështu që në këtë rast e ndërpresim ciklin dhe japim përgjigjen ‘IMPOSSIBLE’.

Detyra

Osmos është një lojë me disa shirita me gjatësi të ndryshme që lëvizin në një fushë si gjarpërinj. Një shirit mund të “gëlltisë” një shirit tjetër nqs gjatësia e tij është më e madhe, dhe në këtë rast gjatësia e shiritit shtohet me gjatësinë e shiritit të gëlltitur.

P.sh. nqs shiriti që po komandojmë ne e ka gjatësinë 10, dhe në fushë janë edhe tre shirita të tjerë me gjatësi 9, 13 dhe 19, fillimisht mund të gëlltisim vetëm shiritin me gjatësi 9. Pas kësaj gjatësia e shiritit tonë bëhet 19, kështu që mund të gëlltisim edhe shiritin me gjatësi 13 (por jo atë me gjatësi 19). Gjatësia e shiritit tonë bëhet 31, kështu që mund të gëlltisim edhe shiritin e fundit me gjatësi 19 dhe loja mbaron.

Programi i lojës në fillim gjeneron shiritin e lojtarit dhe disa shirita të tjerë me gjatësi të rastësishme. Mirëpo është e mundur që me ato gjatësi të gjeneruara rastësisht të mos ketë një mënyrë për ti gëlltitur të gjithë shiritat dhe për të fituar lojën. Kjo situatë mund të rregullohet me këto dy veprime: duke shtuar shtuar një shirit tjetër me gjatësi të caktuar, ose duke hequr ndonjë nga shiritat ekzistues. Cili është numri më i vogël i këtyre veprimeve për ta bërë lojën të zgjidhshme?

P.sh. le ta zëmë se në fillim gjatësia e shiritit të lojtarit është 10 dhe shiritat e tjerë kanë gjatësi [9, 20, 25, 100]. Kjo lojë nuk është e zgjidhshme. Por po të shtojmë një shirit me gjatësi 3 dhe të heqim shiritin me gjatësi 100, mund ta bëjmë të zgjidhshme me vetëm 2 veprime. Përgjigja në këtë rast është 2.

Referenca: https://code.google.com/codejam/contest/dashboard?c=2434486

Shembull

$ cat input.txt
4
2 2
2 1
2 4
2 1 1 6
10 4
25 20 9 100
1 4
1 1 1 1

$ python3 prog.py < input.txt
Case #1: 0
Case #2: 1
Case #3: 2
Case #4: 4

Rreshti i parë i çdo rasti testimi jep gjatësinë e shiritit të lojtarit dhe numrin N të shiritave të tjerë. Rreshti i dytë jep gjatësitë e N shiritave të tjerë.