Problemi 098

Kërkesa

Një lloj petëzash kanë një fytyrë të qeshur të bërë me çokollatë nga njëra anë, dhe asgjë nga ana tjetër. Petëzat janë duke u pjekur të vëna në rresht mbi një sipërfaqe të nxehtë. Në kuzhinë ndodhet një kthyes petëzash që mund të kthejë K petëza njëherësh. Kjo do të thotë që petëzat që janë në anën e fytyrës kthehen nga ana bosh, dhe anasjelltas, por pa ndryshuar radhën e tyre.

Nuk është është e mundur që me këtë lopatëz të kthehen më pak se K petëza, as në anët e rreshtit, sepse sipërfaqja e sobës ka disa të ngritura në anë që e pengojnë këtë. Dmth me këtë lopatëz është e mundur që të kthejmë K petëzat e para të rreshtit, por jo vetëm K-1 petëzat e para.

Nxënësi që ndihmon mjeshtrin, i cili akoma është duke e mësuar zanatin, ka kthyer disa petëza me lopatëzën e vogël, e cila mund të kthejë vetëm një petëz, dhe pastaj shkoi te banaku bashkë me të, pikërisht në kohën që disa klientë janë duke ardhur për të vizituar kuzhinën. Tani mjeshtrit i duhet që ti kthejë sa më shpejt të gjitha petëzat që të jenë me fytyrën e qeshur sipër, duke përdorur lopatëzën e gjerë.

Gjeni numrin më të vogël të kthimeve që duhen për ti bërë të gjitha petëzat me fytyrën sipër, ose thoni që kjo është e pamundur.

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

Shembull

$ cat input.txt
3
---+-++- 3
+++++ 4
-+-+- 4

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

Shenja “-” tregon një petëz me faqen bosh sipër, kurse shenja “+” tregon një petëz me faqen me fytyrë sipër. Numri në fund tregon gjerësinë e lopatëzës (dmth sa petëza mund të kthejë njëherësh).

Në rastin e parë mund të kthejmë në fillim tre petëzat e para, pastaj tre të fundit, pastaj tre petëzat që ngelen me faqen bosh. Dmth me tre kthime mund ti rregullojmë të gjitha.

Në rastin e dytë janë të gjitha në rregull kështu që nuk është nevoja të kthejmë ndonjë gjë.

Në rastin e tretë është e pamundur që ti bëjmë të gjitha petëzat me faqen e duhur lart.

Zgjidhja

for t in range(int(input())):
    S, K = input().split()
    S = list(S)
    K = int(K)
    ans = 0
    i = 0
    while i < len(S) - K + 1:
        if S[i] == '-':
            ans += 1
            for j in range(i, i + K):
                S[j] = ('+' if S[j]=='-' else '-')
        i += 1
    while i < len(S):
        if S[i] == '-':
            ans = 'IMPOSSIBLE'
            break
        i += 1
    print('Case #{}: {}'.format(t+1, ans))

Sqarime

Fillimisht vërejmë se radha e kthimit të petëzave nuk ka rëndësi. Dmth nëse bëjmë një kthim k1 dhe pastaj një kthim k2, rezultati do jetë i njëjtë sikur të bëjmë në fillim kthimin k2 dhe pastaj kthimin k1.

Gjithashtu, nuk ka kuptim që në një vend të caktuar të bëjmë më shumë se një kthim, sepse kthimi i dytë do zhvlerësonte të parin, kështu që më mirë mos ti bënim fare këto dy kthime.

Kjo zgjidhje zbaton një strategji lakmitare (greedy). Nqs petëza që ndodhet e para nga e majta është “-” atere duhet patjetër një kthim i K petëzave të para për ta vendosur në rregull. Meqenëse dy kthime në të njëjtin vend s’kanë kuptim, atere vazhdojmë me petëzën e dytë dhe përsërisim të njëjtën gjë. Nqs pas kthimit të fundit ka mbetur ndonjë petëz e pa rregulluar nga K petëzat e fundit, atere është e pamundur që të rregullohen të gjitha petëzat.

Meqenëse kemi dy cikle brenda njëri-tjetrit, koha e kësaj zgjidhje është e madhësisë \(O(N^2)\). Rasti më i keq është kur K=N/2. Zgjidhja më poshtë e ka kohën të madhësisë \(O(N)\).

Zgjidhja 2

for t in range(int(input())):
    S, K = input().split()
    S = list(S)
    K = int(K)
    M = [0 for i in range(len(S) + K)]
    flips = 0
    i = 0
    while i < len(S) - K + 1:
        flips -= M[i]
        if (flips % 2 == 0 and S[i] == '-') or (flips % 2 == 1 and S[i] == '+'):
            flips += 1
            M[i+K] = 1
        i += 1
    ans = sum(M)
    while i < len(S):
        flips -= M[i]
        if (flips % 2 == 0 and S[i] == '-') or (flips % 2 == 1 and S[i] == '+'):
            ans = 'IMPOSSIBLE'
            break
        i += 1
    print('Case #{}: {}'.format(t+1, ans))

Sqarime

Kjo zgjidhje arrin një kohë të rendit \(O(N)\) duke mos i kthyer të gjitha petëzat por duke kthyer vetëm të parën dhe duke mbajtur shënim numrin e herëve që duhen kthyer petëzat pasardhëse. P.sh. nqs K=5 dhe petëza e parë është “-”, atere ne nuk kthejmë 5 petëzat e para, por kthejmë vetëm të parën, shtojmë 1 te flips për të ditur që petëzat pasardhëse do kthehen një herë, dhe mbajmë shënim 1 te M në pozicionin e gjashtë, për të ditur që duhet ta pakësojmë flips me 1 kur të vijmë te petëza e gjashtë.

Vazhdojmë në këtë mënyrë për çdo petëz dhe shikojmë nëse flips është çift dhe prapë petëza është “-” atere duhet kthyer. Po ashtu, nëse flips është tek dhe petëza është “+” atere duhet kthyer edhe një herë.

Njëlloj si në zgjidhjen e mëparshme, nëse ka mbetur ndonjë petëz e pa rregulluar nga K petëzat e fundit, atere është e pamundur që të rregullohen të gjitha petëzat.

Detyra

Vanesa ka N xhingla në raftin e saj, të numëruara 1, 2, …, N nga e majta në të djathtë. Xhinglat janë të llojeve të ndryshme, ku çdo lloj shënohet me një numër. Xhingla që ndodhet në pozicionin i në raftin e saj është e llojit \(A_i\).

Vanesa studion jashtë dhe sot do kthehet që të vizitojë familjen. Ajo do që të marrë sa më shumë xhingla me vete, por ngaqë është me nxitim i duhet të rrëmbejë një varg të vazhdueshëm xhinglash. Po ta themi me gjuhë shkencore, Vanesa zgjedh me mënd dy pozicione l dhe r dhe vërvit në çantë të gjitha xhinglat që ndodhen në vendet \(l, l+1, ..., r-1, r\). Gjithashtu, për shkak të rregullave të aeroportit, kontrolluesit do hedhin poshtë të gjitha xhinglat e një lloji të caktuar, nëse ajo ka më shumë se S të tilla.

P.sh. nqs S = 2 dhe Vanesa ka me vete 6 xhingla, një të llojit 0, dy të llojit 1, dhe tre të llojit 2, asaj do ti lejohen xhinglat e llojit 0 dhe 1, por do ti hidhen poshtë të treja xhinglat e llojit 2.

Vanesa duhet të zgjedhë l dhe r të tilla që të marrë sa më shumë xhingla me vete. Sa është numri më i madh i xhinglave që mund të marrë me vete Vanesa?

Referenca: https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050eda/00000000001198c1

Shembull

$ cat input.txt
4
6 2
1 1 4 1 4 4
8 1
1 2 500 3 4 500 6 7
10 1
100 200 8 8 8 8 8 300 400 100
12 2
40 50 1 1 1 60 70 2 2 2 80 90

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

Për çdo rast testimi jepet numri i xhinglave N dhe maksimumi i lejuar në aeroport S. Pastaj jepet vargu i xhinglave sipas llojit të secilës prej tyre.

Në rastin e parë Vanesa duhet të zgjedhë l=2 dhe r=5. Kjo i lejon asaj të marrë xhinglat [1, 4, 1, 4], asnjë prej të cilave nuk hidhet poshtë në aeroport.

Në rastin e dytë Vanesa duhet të zgjedhë l=1 dhe r=8. Xhinglat e llojit 500 do hidhen poshtë meqë janë më shumë se S=1 të tilla, kështu që ajo do marrë me vete 6 xhingla.

Në rastin e tretë duhet të zgjedhë l=1 dhe r=9 dhe të sjellë në aeroport xhinglat [100, 200, 8, 8, 8, 8, 8, 300, 400]. Xhinglat e llojit 8 do hidhen poshtë dhe do ti ngelen 4 xhingla me vete.

Në rastin e katërt duhet të zgjedhë l=1 dhe r=12. Xhinglat e llojit 1 dhe 2 do hidhen poshtë meqë ka më shumë se S=2 të tilla, kështu që do ti mbeten 6 xhingla.