Problemi 117

Kërkesa

Në një lojë kemi N monedha të numëruara nga 1 në N, dhe fillimisht të gjitha monedhat janë nga e njëjta anë (H ose T). Loja luhet me N raunde, dhe në çdo raund k, lojtari kthen k monedhat e para (nga 1 deri në k) në anën tjetër. Duam të gjejmë se sa monedha do jenë në një anë të caktuar (H ose T) në fund të lojës.

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

Shembull

$ cat input.txt
2
1 5 1
1 5 2

$ python3 prog.py < input.txt
2
3

Kemi 2 raste testimi. Në rastin e parë kemi I=1, N=5, Q=1, që do të thotë se fillimisht monedhat janë të gjitha në anën H, kemi 5 monedha dhe 5 raunde, dhe në fund të raundit të 5-të duam të dimë se sa monedha janë në anën H.

Në rastin e dytë është e njëjta gjë, vetëm se duam të dimë se sa monedha janë në anën T (Q=2).

Gjendja e monedhave pas çdo raundi do jetë e tillë: 1. T H H H H 2. H T H H H 3. T H T H H 4. H T H T H 5. T H T H T

Kështu që përgjigja për rastin e parë është 2, kurse për rastin e dytë është 3.

Zgjidhja 1

for _ in range(int(input())):
    I, N, Q = map(int, input().split())
    L = ['H']*N if I==1 else ['T']*N
    for r in range(N):    # for each round
        for i in range(r+1):
            # flip coin
            if L[i] == 'H':
                L[i] = 'T'
            else:
                L[i] = 'H'
        #print(L)    # debug
    nr = 0
    for i in range(N):
        if (Q == 1 and L[i] == 'H') or (Q == 2 and L[i] == 'T'):
            nr += 1
    print(nr)

Zgjidhja 2

for _ in range(int(input())):
    I, N, Q = map(int, input().split())
    nr = N // 2
    if N % 2 != 0 and I != Q:
        nr += 1
    print(nr)

Sqarime

Zgjidhja e parë është e rendit \(O(N^2)\), që do të thotë se duhen kryer përafërsisht \(N^2\) veprime. Kur \(N\) bëhet e madhe, \(N^2\) bëhet shumë shpejt jashtëzakonisht e madhe.

Kurse zgjidhja e e dytë është e rendit \(O(C)\), që do të thotë se nuk ka rëndësi se sa e madhe është N-ja, ne mund ta gjejmë gjithmonë përgjigjen me një numër konstant veprimesh.