Problemi 083

Kërkesa

Në koncertin e operas këngëtarja kryesore është një mikja juaj. Ju doni të siguroheni që në fund të shfaqjes e gjithë salla të ngrihet në këmbë dhe të duartrokasë.

Në fillim spektatorët janë të ulur. Çdo spektator ka një nivel turpi. Një spektator me nivel turpi \(S_i\) pret deri sa të paktën \(S_i\) spektatorë të tjerë të jenë çuar në këmbë duke duartrokitur, pastaj çohet edhe ai. Nëse \(S_i = 0\) atere spektatori çohet gjithmonë në këmbë për të duartrokitur, pavarësisht nëse është çuar ndonjë tjetër. Nëse një spektator e ka \(S_i = 2\) atere pret deri sa të çohen të paktën 2 të tjerë, para se të çohet.

Ju e njihni nivelin e turpit të spektatorëve që do shkojnë në koncert dhe mund të ftoni edhe njerëz të tjerë me një nivel turpi të çfarëdoshëm, jo domosdoshmërisht të njëjtë. Sa është numri më i vogël i njerëzve që duhet të ftoni për të garantuar që e gjithë salla do çohet në këmbë.

Referenca: https://code.google.com/codejam/contest/6224486/dashboard#s=p0

Shembull

$ cat input.txt
4
4 11111
1 09
5 110011
0 1

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

Për çdo rast testimi jepet niveli më i lartë i turpit, dhe pastaj jepet një varg numrin e spektatorëve për secilin nivel, duke filluar nga 0. P.sh. “409” do të thotë që 4 persona kanë nivel turpi 0, asnjë me nivel turpi 1, dhe 9 me nivel turpi 2.

Në rastin e parë e gjithë salla do çohet në këmbë pa shtuar asnjë të ftuar tjetër.

Në rastin e dytë, duhet të ftojmë një person me nivel turpi 0, dhe pastaj 9 të tjerët do çohen në këmbë, meqë e kanë nivelin 1.

Në rastin e tretë mund të ftojmë një person me nivel 2 dhe një me nivel 3, ose 2 persona me nivel 2. Të dyja këto raste bëjnë që edhe spektatori me nivel 4 të çohet në këmbë, dhe pas atij edhe spektatori me nivel 5.

Zgjidhja 1

for t in range(int(input())):
    _, audience = input().split()
    extra = 0
    invite = 0
    for i in range(len(audience)):
        if audience[i] == '0':
            if extra > 0:
                extra -= 1
            else:
                invite += 1
        else:
            extra += int(audience[i]) - 1
    print('Case #{}: {}'.format(t+1, invite))

Sqarime

Në ndryshoren invite mbajmë numrin e personave që duhen ftuar. Në ndryshoren extra mbajmë numrin e personave që janë më tepër se sa duhen për të ngritur në këmbë personat e nivelit i.

Zgjidhja bazohet në faktin që po të kemi të paktën një person për çdo nivel, atere të gjithë do ngrihen në këmbë. Nqs kemi më shumë se 1 person për një nivel të caktuar, atere personat “e tepërt” i shtojmë te extra. Në rast se kemi 0 persona për një nivel të caktuar, atere këtë mund ta kompensojmë me një person nga ata që janë te extra, por nqs edhe vetë extra është bosh (0), atere për të zgjidhur situatën duhet të ftojmë një person tjetër.

Zgjidhja 2

for t in range(int(input())):
    _, audience = input().split()
    up = 0
    invite = 0
    for i in range(len(audience)):
        invite = max(invite, i - up)
        up += int(audience[i])
    print('Case #{}: {}'.format(t+1, invite))

Sqarime

Në ndryshoren up mbajmë shënim personat që janë çuar deri në një nivel të caktuar (dhe e shtojmë për çdo nivel). Nqs ky numër është më i vogël se niveli i, atere na duhet të ftojmë (i - up) persona të tjerë, në mënyrë që këta të nivelit i të çohen në këmbë. Personat e ftuar mund të jenë të gjithë të nivelit 0, dmth që çohen menjëherë në këmbë. Meqenëse për çdo nivel i llogarisim numrin e personave që duhet të ftojmë për këtë nivel, atere mjafton që të ftojmë maksimumin e këtyre numrave, dhe kjo do bëjë që personat e çdo niveli të ngihen në këmbë. Pra ne gjejmë maksimumin e vlerës për shprehjen (i - up).

Detyra

Një arë është e ndarë në parcela, të cilat formojnë N rreshta (nga 1 në N) dhe M shtylla (nga 1 në M). Nga këto, vetëm K parcela janë të mbjella, kurse të tjerat janë me barishte. Dy parcela quhen fqinje nëse kanë një anë të përbashkët. Duam të ndërtojmë një gardh që rrethon parcelat e mbjella, në mënyrë të tillë që të mos ketë gardh midis dy parcelave të mbjella por vetëm midis një parcele të mbjellë dhe një të pambjellë, ose midis një parcele të mbjellë dhe pjesës jashtë arës. Sa është numri më i vogël i anëve ku duhet ndërtuar gardh?

Referenca: https://www.codechef.com/APRIL19B/problems/FENCE

Shembull

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

$ python3 prog.py < input.txt
20
4

Për çdo rast testimi jepen N, M dhe K. Më pas vijnë K rreshta me nga dy numra r dhe s, që janë rreshti dhe shtylla e një parcele të mbjellë.

Në rastin e parë fusha duket e tillë (ku me x është shënuar një parcelë e mbjellë dhe me - një parcelë e pambjellë:

---x
xxx-
x-x-
xxx-

Një zgjidhje optimale është që të ndërtohet gardh rreth parcelës lart në cep (4 anë), pastaj rreth grupit të parcelave të mbjella poshtë (12 anë), si dhe rreth parcelës së pambjellë në qendër (4 anë). Gjithsej 4 + 12 + 4 = 20 anë.