Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | jetoane2.in, jetoane2.out | Sursă | Winter Challenge 2008, Runda 1 |
| Autor | Bogdan Alexandru Stoica | Adăugată de |  Bogdan-Alexandru Stoica •fireatmyself |
| Timp execuţie pe test | 0.275 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Jetoane 2
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 M 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 (de maxim M litere) 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 pi. Mai mult, WW nu poate alege orice subsecventa, ci doar una aflata in lista de N mutari valide (care se obtinue 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.
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.
Date de intrare
Pe prima linie a fisierului jetoane2.in se afla 26 de numere naturale, mai mici decat 10000, reprezentand ponderea fiecarei litere. Pe a doua linie se afla M, numarul de jetoane, urmat, pe a treia linie, de sirul initial de jetoane (un sir de M litere mici). Pe a patra linie se afla nr de mutari valide, N, iar pe urmatoarele N linii se afla cate un sir de maxim 10 caractere, reprezentad descrierea unei mutari.
Date de iesire
Pe prima linie a fisierului jetoane2.out se va afla numarul maxim cerut de WW.
Restrictii
- 1 ≤ M, N ≤ 150
- toate literele din fisierul de intrare vor fi litere mici ale alfabetului englez
- doua litere pot avea aceeasi pondere
- pentru 40% din teste 1 ≤ M, N ≤ 50
- pentru simplitatea si cursivitatea citirii enuntului WW se poate citi Dublu V
Exemplu
| jetoane2.in | jetoane2.out |
|---|---|
| 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 |
Explicatie
Initial sirul este "aabcdee". WW extragere 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.
