Fişierul intrare/ieşire:strigat.in, strigat.outSursăSummer Challenge 2007, runda 1
AutorDin FolclorAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.275 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Strigat

La insistentele aghiotantului sau Arthur, Tick s-a decis sa renunte la strigatul sau de lupta "Lingura". Tick vrea ca strigatul sau sa fie cat mai inspaimantator pentru raufacatorii din oras. Tick stie ca exista M cuvinte care ii sperie pe raufacatori si care daca se vor afla in cadrul strigatului sau provoaca un anumit grad de spaima. Se cunoaste pentru fiecare cuvant gradul de spaima pe care il provoaca Ai. Gradul total de spaima al strigatului va fi A1*n1 + A2*n2 + ... + AM*nM, unde ni este numarul de aparitii al cunvatului i in cadrul strigatului. Atentie aparitiile cuvintelor se pot suprapune.

Cerinta

Ajutati-l pe Tick sa isi gaseasca un strigat de lupta format din N caractere si care provoaca un grad maxim de spaima.

Date de intrare

Pe prima linie a fisierului de intrare strigat.in se afla doua numere intregi N si M cu semnificatiile din enunt. Urmeaza apoi M perechi de linii pe prima aflandu-se un cuvant, iar pe a doua gradul de spaima pe care il induce o aparitie a sa.

Date de iesire

Pe prima linie a fisierului de iesire strigat.out se afla gradul maxim de spaima pe care il induce un strigat de lungime N. Pe a doua linie se va afla un strigat care induce gradul respectiv de spaima.

Restrictii

  • 1 ≤ N ≤ 100
  • 0 ≤ M ≤ 100
  • 1 ≤ lungimea unui cuvant ≤ 100
  • 0 ≤ Ai ≤ 1000
  • printre cele M cuvinte nu vor exista 2 identice
  • pentru gasirea doar a gradului maxim de spaima se va acorda 40% din punctaj.

Exemplu

strigat.instrigat.out
4 2
aa
5
ab
6
16
aaab

Explicatie

aa apare de 2 ori(incepand cu prima respectiv cu a doua pozitie), ab apare o singura data deci spaima totala este 5*2+6=16.
Nici un alt strigat nu poate atinge o valoare mai mare.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content