== include(page="template/taskheader" task_id="jetoane2") ==
Poveste si cerinta...
Dupa mai multe incercari esuate de a castiga la Loto, WW decide sa renunte si sa se apuce de jocuri de noroc. A deprins repede experienta si chiar a inceput sa castige bani frumosi (sumele dobandite sunt strict confidentiale). Nu conteaza cum a reusit ca intr-un timp atat de scurt sa invete atat de multe, ce conteaza, insa, este ca zilele trecute WW a dat peste un joc destul de incurcat. El are in fata un numar de jetoane, puse unul langa celalalt, pe care sunt inscriptionate literele mici ale alfabetului englez (cate o litera pe fiecare jeton). El poate executa urmatoarea mutare asupra sirului: alege o subsecventa, din acest sir, pe care o extrage, apoi alatura (daca exista) cele doua bucati ramase. Pentru ca jocul sa fie si mai palpitant, fiecare litera are o pondere $p{~i~}$. Mai mult, WW nu poate alege orice subsecventa, ci doar una aflata in lista de $N$ mutari valide (care se obtine la inceputul jocului printr-un algoritm neinteresant). O mutare valida este reprezentata de un sir de maxim $10$ caractere. Cand WW a extras o anumita subsecventa el primeste un scor numeric egal cu suma ponderii fiecarei litere ce compune subsecventa.
h2. Cerinta
WW va pune la dispozitie sirul de jetoane, ponderile fiecarei litere, precum si lista cu mutarile valide. Va roaga sa-l ajutati a determina scorul maxim pe care poate sa-l obtina.
h2. Date de intrare
Fisierul de intrare $jetoane2.in$ ...
Pe prima linie a fisierului $jetoane2.in$ se afla $26$ de numere naturale, mai mici decat $1000$, reprezentand ponderea fiecarei litere. Pe a doua linie se afla sirul initial de jetoane urmat, pe a treia linie, de numarul de mutari valide, $N$. Pe urmatoarele $N$ linii se afla cate un sir de maxim $10$ caractere, reprezentad descrierea unei mutari.
h2. Date de iesire
In fisierul de iesire $jetoane2.out$ ...
Pe prima linie a fisierului $jetoane2.out$ se va afla numarul maxim cerut de WW.
h2. Restrictii
* $... ≤ ... ≤ ...$
* {$1 ≤ N ≤ 170$}
* {$1 ≤ lungimea sirului initial ≤ 170$}
* toate literele din fisierul de intrare vor fi litere mici ale alfabetului englez
* doua litere pot avea aceeasi pondere
* pentru $30%$ din teste $N ≤ 9$
* pentru simplitatea si cursivitatea enuntului WW se poate citi _Dubluveu_
h2. Exemplu
table(example). |_. jetoane2.in |_. jetoane2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|2 5 3 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
aabcdee
5
ab
cd
be
ae
acd
| 19 |
h3. Explicatie
...
Initial sirul este "{$aabcdee$}". WW extrage intai sirul "{$cd$}" ("{$aab ee$}"), obtinandu-se sirul "{$aabee$}" si costul {$1+3=4$}. Urmatorea mutare este extragerea sirului "{$be$}" ("{$aa e$}"), obtinandu-se sirul "{$aae$}" si costul {$4+(5+4)=13$}. Ultima subsecventa extrasa este "{$ae$}", sirul devenind "{$a$}" si costul final, {$13+(2+4)=19$}.
== include(page="template/taskfooter" task_id="jetoane2") ==
