Fişierul intrare/ieşire:jetoane2.in, jetoane2.outSursăWinter Challenge 2008, Runda 1
AutorBogdan Alexandru StoicaAdăugată defireatmyselfBogdan-Alexandru Stoica fireatmyself
Timp execuţie pe test0.55 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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 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 pi. 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.

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 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.

Date de iesire

Pe prima linie a fisierului jetoane2.out se va afla numarul maxim cerut de WW.

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

Exemplu

jetoane2.injetoane2.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 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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content