Problemi 095

Kërkesa

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ë.

Zgjidhja

def make_solvable(A, L):
    """A is the size of the mot of the player, L is a sorted list of the
    mots according to their size. Find and return the minimal number
    of moves that can make this case solvable.

    """
    # If the list of mots is empty, we are done.
    if not L: return 0

    # If A is 1, the only way to make it solvable is to delete all the
    # mots, because it cannot absorb any mot and we cannot inrease its
    # length.
    if A == 1: return len(L)

    # If A > L[0], we can absorb it without any additions or deletions.
    if A > L[0]:
        return make_solvable(A + L[0], L[1:])

    # At this point we have A <= L[0]. We can either add mots (in
    # front of L[0]) until we can absorb it, or delete all the
    # remaining mots. Deleting just the first mot will not improve
    # the situation, since the next one is not smaller than it. The
    # same goes for deletting any other mots.
  
    # Let's find the number of mots we have to insert in order to
    # absorb L[0].
    nr = 0   # nr of mots we have to insert  
    while A <= L[0]:
        nr += 1
        A += A - 1

    # If number of motes we have to insert is greater than the
    # remaining mots, we better just delete the remaining mots, and
    # then we are done.
    if nr >= len(L):
        return len(L)
    
    # Find the number of changes if we absorb the first mot and continue.
    nr1 = make_solvable(A + L[0], L[1:])

    # Return the smallest number of deleting all mots
    # or absorbing the first one and continuing.
    return min(nr + nr1, len(L))

for t in range(int(input())):
    A, N = [int(i) for i in input().split()]
    L = [int(i) for i in input().split()]
    L.sort()
    print('Case #{}: {}'.format(t+1, make_solvable(A, L)))

Detyra

Në një rrugë janë N + 2 vende parkimi në një rresht të vetëm. Vendi i parë dhe i fundit janë gjithmonë të zënë nga policia bashkiake, kurse N të tjerat janë për përdoruesit.

Kur vjen një person për të parkuar ai përpiqet të zërë një vend që të jetë sa më larg nga makinat e tjera. Për të shmangur ngatërresat ata ndjekin disa rregulla të paracaktuara. Për çdo vend parkimi bosh \(V\) llogarisin vlerat \(M_V\) dhe \(D_V\), që janë numrat e vendeve bosh midis këtij vendi dhe vendeve të zëna në të majtë dhe në të djathtë. Pastaj shqyrtojnë ato vende që kanë fqinjin më të largët, dmth ato vende \(V\) për të cilat \(min(M_V, D_V)\) është maksimale. Nëse është vetëm një vend i tillë, atere atë zgjedhin. Përndryshe zgjedhin prej tyre atë vend që e ka vlerën \(max(M_V, D_V)\) maksimale. Nëse prapë ka disa vende të tilla, atere zgjedhin atë prej tyre që është sa më majtas.

Në parkim vijnë K persona. Secili prej tyre parkon para se të vijë personi pasardhës (duke ndjekur rregullat më sipër), dhe asnjë prej tyre nuk largohet.

Kur parkon personi i fundit, sa do jenë vlerat \(max(M_V, D_V)\) dhe \(min(M_V, D_V)\)?

Referenca: https://code.google.com/codejam/contest/3264486/dashboard#s=p2&a=2

Shembull

$ cat input.txt
7
4 2
5 2
6 2
1000 1000
1000 1
1000000 500000
1000000000000000000 500000000000000000

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

Për çdo rast testimi jepen numrat N dhe K.

Në rastin e parë situata është e tillë: 0.12.0 (me 0 shënojmë makinat e policisë, me pikë (.) shënojmë vendet bosh, dhe me numrat 1 dhe 2 shënojmë vendet që kanë zënë i pari dhe i dyti). Kështu që përgjigja është “1 0”.

Në rastin e dytë situata është e tillë: 02.1..0, kështu që përgjigja është “1 0”.

Në rastin e tretë situata është e tillë: 0..1.2.0, kështu që përgjigja është “1 1”.

Në rastin e katërt çdo vend do jetë i zënë në fund, pavarësisht nga radha se si zihen, kështu që përgjigja është “0 0”.