Problemi 057

Kërkesa

Në spektaklin “Kujt ia mban të jetë milioner?” (“Who dares to be a millionaire?”) bëhen N pyetje, ku çdo pyetje ka 26 alternativa që shënohen me shkronjat A-Z, nga të cilat vetëm njëra është e saktë. Pjesëmarrësit i dinë pyetjet që do bëhen dhe e kanë ndarë mendjen për përgjigjet që do japin, por pa e ditur nëse këto përgjigje janë të sakta.

Loja bëhet kështu. Në fillim pyetjet përzihen në mënyrë që radha e tyre të jetë e rastësishme. Pastaj pyetjet i drejtohen një nga një pjesëmarrësit. Nëse përgjigja është e saktë, vazhdohet me pyetjen tjetër, përndryshe loja mbaron.

Lojtari shpërblehet në këtë mënyrë. Nëse s’ka dhënë asnjë përgjigje të saktë merr shpërblimin \(W_0\), nëse ka dhënë 1 përgjigje të saktë shpërblimi është \(W_1\), për 2 përgjigje të sakta shpërblimi është \(W_2\), e kështu me radhë. Vetëm se nuk është e thënë që \(W_{i+1} > W_i\) (mesa duket kjo lojë do jetë shpikur nga ndonjë i lojtur).

Nqs dimë përgjigjet e sakta për çdo pyetje, përgjigjet e një lojtari, dhe vlerat e shpërblimeve, sa është shpërblimi më i madh që mund të fitojë ky lojtar?

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

Shembull

$ cat input.txt
3
5
ABCDE
EBCDA
0 10 20 30 40 50
4
CHEF
QUIZ
4 3 2 1 0
8
ABBABAAB
ABABABAB
100 100 100 100 100 100 100 100 100

$ python3 prog.py < input.txt
30
4
100

Në rastin e parë, nëse pyetjet renditen sipas radhës (2, 3, 4, 5, 1), atere lojtari do japë 3 përgjigje të sakta dhe do fitojë 30 pikë.

Në rastin e dytë, sido që të renditen pyetjet lojtari nuk ka asnjë përgjigje të saktë, kështu që do fitojë \(W_0\).

Në rastin e tretë, sado përgjigje të sakta të japë, nuk ka për të fituar veçse 100 pikë.

Zgjidhja 1

T = int(input())
for _ in range(T):
    n = int(input())
    Q = input()
    A = input()
    W = list(map(int, input().split()))
    c = 0
    for i in range(n):
        if Q[i] == A[i]:
            c += 1
    if c == n:
        print(W[n])
    else:
        wmax = W[0]
        for i in range(c+1):
            if W[i] > wmax:
                wmax = W[i]
        print(wmax)

Sqarime

Fillimisht gjejmë se sa është numri i përgjigjeve të sakta (c – correct). Nëse të gjitha përgjigjet janë të sakta, atere shpërblimi i vetëm i mundshëm është \(W[n]\), përndryshe të gjitha shpërblimet janë të mundshme, nga \(W_0\) te \(W_c\). Dhe meqenëse \(W\) nuk është e thënë të jetë e renditur në rendin rritës, duhet të gjejmë se cila është vlera më e madhe nga këto.

Zgjidhja 2

for _ in range(int(input())):
    n = int(input())
    Q = input()
    A = input()
    W = [int(w) for w in input().split()]
    c = 0
    for i in range(n):
        if Q[i] == A[i]:
            c += 1
    print(W[n]) if c==n else print(max(W[0:c+1]))

Sqarime

Është e njëjta zgjidhje por pak më ndryshe. W[0:c+1] është një nënlistë e listës W, me elementet nga 0 deri në c. Kurse funksioni max() gjen vlerën më të madhe të një liste.

Detyra

Bëni një program që kontrollon nëse një varg numrash plotëson këto kushte:

• Ka një qendër (dmth numri i elementeve në të majtë të qendrës është i barabartë me numrin e elementeve në të djathtë).
• Numri i parë dhe i fundit është 1.
• Duke u nisur nga qendra, numrat në të majtë dhe në të djathtë vijnë duke zbritur me nga 1.

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

Shembull

$ cat input.txt
7
5
1 2 3 2 1
7
2 3 4 5 4 3 2
5
1 2 3 4 3
5
1 3 5 3 1
7
1 2 3 4 3 2 1
4
1 2 3 2
4
1 2 2 1

$ python3 prog.py < input.txt
yes
no
no
no
yes
no
no