Problemi 056

Kërkesa

Një lojë luhet në një shirit letre të ndarë në kuti, ku në çdo kuti është shënuar nga një numër natyror. Fillimisht lojtari i parë ngjyros një kuti (ku të dojë), pastaj lojtari i dytë mund të presë një kuti në skajet e shiritit (nqs është e pangjyrosur), pastaj lojtari i parë ngjyros një kuti tjetër që është ngjitur me një kuti të ngjyrosur më parë, pastaj lojtari i dytë pret një kuti tjetër të pangjyrosur, e kështu me radhë. Pra lojtari i parë në fillim ngjyros ku të dojë, por pastaj duhet të ngjyros një kuti ngjitur me kutitë e ngjyrosura më parë. Kurse lojtari i dytë mund të presë një kuti në skajet e letrës, por jo nqs është e ngjyrosur.

Qëllimi i lojtarit të parë është që shuma e numrave në kutitë e ngjyrosura të jetë sa më e madhe. Bëni një program që gjen se sa janë pikët maksimale që mund të fitojë lojtari i parë në këtë lojë.

Referenca: https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050ee2/000000000005118a

Shembull

$ cat input.txt
4
4
1332
4
9583
3
616
10
1029384756

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

Në rastin e parë kemi katër numrat 1332. Lojtari i parë mund të ngjyrosë dy të mesit dhe të fitojë 6 pikë.

Në rastin e dytë kemi numrat 9583. Numri më i madh i pikëve fitohet nëse ngjyrosen dy kutitë e para.

Në rastin e tretë mund të ngjyroset fillimisht njëshi dhe pastaj një nga gjashtat.

Në rastin e katërt është e mundur të ngjyrosen **93847*, që japin dhe shumën maksimale 31.

Zgjidhja 1

T = int(input())
for t in range(1, T+1):
    N = int(input())
    W = input()
    s = (N + 1) // 2
    B = 0
    for i in range(N-s):
        b = 0
        for j in range(s):
            b += int(W[i+j])
        if b > B:
            B = b
    print("Case #{}: {}".format(t, B))

Sqarime

Po ta shikojmë me kujdes problemin dhe të bëjmë disa prova, mund të bindemi që lojtari i parë gjithmonë mund të ngjyrosë gjysmat e kutive. Bile, nqs numri N i kutive është tek, ai mund të ngjyrosë (N+1)//2, meqenëse luan i pari.

Po ashtu, nqs arsyetojmë pak, mund të bindemi që lojtari i parë mund të ngjyrosë ato kuti të njëpasnjëshme që dëshiron. P.sh. në shembullin e katërt loja mund të zhvillohet kështu. Në fillim ngjyroset kutia me numrin 8. Pastaj, nqs pritet një kuti nga e djathta atere vazhdohet me ngjyrosjen e numrit 4, përndryshe vazhdohet me ngjyrosjen e numrit 3. Në këtë mënyrë mund të ngjyrosim ato kuti që duam pavarësisht se nga cila anë priten kutitë.

Meqenëse mund të ngjyrosim gjysmat e kutive, dhe mund të zgjedhim ato kuti të njëpasnjëshme që duam, atere problemi i gjetjes së shumës maksimale bëhet më i thjeshtë. Programi gjen në fillim shumën e gjysmës së parë të kutive, pastaj i zhvendos kutitë e ngjyrosura me një kuti në të djathtë dhe shikon nëse shuma e re është më e madhe se maksimumi i tanishëm, e kështu me radhë.

Zgjidhja 2

T = int(input())
for t in range(1, T+1):
    N = int(input())
    W = input()
    s = (N + 1) // 2
    B = 0
    for i in range(s):
        B += int(W[i])
    b = B
    for i in range(N-s):
        b -= int(W[i])
        b += int(W[s+i])
        if b > B:
            B = b
    print("Case #{}: {}".format(t, B))

Sqarime

Zgjidhja e parë ka dy cikle brenda njëri-tjetrit, ku secili cikël përsëritet N/2 herë. Kështu që kompleksiteti i saj është i rendit \(O(N^2)\)

Kurse zgjidhja e dytë ka dy cikle që përsëriten N/2 herë, por që nuk janë brenda njëri-tjetrit. Kështu që kompleksiteti i saj është i rendit \(O(N)\).

Zgjidhja e dytë është shumë më e shpejtë se zgjidhja e parë.

Detyra

Një lojë luhet në një tabelë drejtkëndore me N rreshta dhe M shtylla. Fillimisht kutitë e tabelës janë të pangjyrosura. Lojtari fillon ti ngjyrosë një nga një, dhe për çdo kuti që ngjyros merr aq pikë sa fqinjë të ngjyrosur ka kjo kuti (fqinjët e një kutie janë ato kuti që kanë një brinjë të përbashkët me të). Shuma e këtyre pikëve janë pikët që fitohen nga kjo lojë. Bëni një program që gjen se sa janë pikët maksimale që mund të fitohen në këtë lojë.

Referenca: https://www.codechef.com/problems/OMWG

Shembull

$ cat input.txt
1
2 2

$ python3 prog.py < input.txt
4

Në një tabelë me 2 rreshta dhe 2 shtylla, numri maksimal i pikëve që mund të fitohen është 4.