Problemi 146

Kërkesa

Kemi një listë me pikë (numra natyrorë) të shkruara në një shirit të tejdukshëm. Kemi edhe një shirit me veprime modifikuese, me gjatësi më të madhe se lista e pikëve, mbi të cilin mund të vendoset shiriti i tejdukshëm dhe të llogariten veprimet totale.

Shiriti modifikues ka këto veprime:

• Pikë (.): nuk bën asnjë modifikim.
• Dyfisho pikët (d): dyfishon numrin e pikëve që përputhen me të.
• Trefisho pikët (t): trefishon numrin e pikëve që përputhen me të.
• Dyfisho totalin (D): dyfishon shumën e të gjitha pikëve, dhe zbatohet në fund.
• Trefisho totalin (T): trefishon shumën e të gjitha pikëve, dhe zbatohet në fund.

Shiriti me pikë vendoset mbi shiritin e modifikuesve në një pozicion të caktuar dhe bëhet shuma e pikëve, duke e dyfishuar ose trefishuar numrin e pikëve më parë, nëse përputhen me veprimet d dhe t. Kurse veprimet D dhe T bëjnë dyfishimin ose trefishimin e shumës totale dhe zbatohen gjithmonë në fund.

Gjeni pozicionin që jep vlerën më të madhe totale të pikëve dhe thoni sa është ajo vlerë.

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

Shembull

$ cat input.txt
2
10
..d.t.D..d
10 11 12 9 8 10 11 15
22
dtDtTD..ddT.TtTdDT..TD
12297 5077 28888 17998 12125 27400 31219 21536

$ python3 prog.py < input.txt
270
35629632

Zgjidhja

for _ in range(int(input())):
    n = int(input())
    B = input()
    L = [int(i) for i in input().split()]
    max_score = 0
    for i in range(n - len(L) + 1):
        L1 = []
        B1 = []
        for j in range(len(L)):
            c = B[i+j]
            if c == '.':
                L1.append(L[j])
            elif c == 'd':
                L1.append(2*L[j])
            elif c == 't':
                L1.append(3*L[j])
            else:
                L1.append(L[j])
                B1.append(c)
        score = sum(L1)
        for c in B1:
            if c == 'D':
                score *= 2
            else:
                score *= 3
        if score > max_score:
            max_score = score
    print(max_score)