Fişierul intrare/ieşire:carte.in, carte.outSursăONIS 2014, Runda 1
AutorTeodor PlopAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.35 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Carte

Chiar dacă mai sunt câteva zile până la Crăciun, moşul i-a adus deja cadourile lui Georgică, pentru că a fost foarte cuminte. Acesta a găsit sub brad o carte, intitulată "Cartea fără spaţii". După cum îi spune şi numele, cartea conţine cuvinte, care însă nu sunt separate între ele. Astfel, vom spune că ea este formată dintr-un şir de litere mici ale alfabetului englez. Pentru a înţelege mesajul cărţii cât mai bine, Georgică trebuie să separe cuvintele între ele, astfel încât suma lungimilor cuvintelor pe care nu le înţelege să fie minimă. Georgică înţelege un cuvânt, daca acesta se află în dicţionarul limbii sale.

Dându-se numărul de teste T, iar pentru fiecare test conţinutul cărţii, numărul de cuvinte ale dicţionarului N şi cele N cuvinte din dicţionar, să se spună care este suma minimă a lungimilor cuvintelor pe care Georgică nu le inţelege după ce separă textul într-un mod convenabil.

Date de intrare

Fişierul de intrare carte.in conţine pe prima linie T, numărul de teste. În continuare, pentru fiecare test, se va găsi pe prima linie şirul reprezentând conţinutul cărţii, pe a doua linie numărul natural N, iar pe următoarele N linii, câte un cuvânt din dicţionarul lui Georgică.

Date de ieşire

În fişierul de ieşire carte.out se vor găsi T linii, pe linia i găsindu-se răspunsul pentru testul i.

Restricţii

  • T = 10
  • 1 ≤ N ≤ 1.000
  • Cartea nu conţine mai mult de 3.000 caractere.
  • Cuvintele din dicţionar vor avea cel mult 3.000 caractere.
  • Dicţionarul lui Georgică poate conţine două cuvinte identice.

Exemplu

carte.incarte.out
1
abcd
3
ab
bc
a
1

Explicaţie

Georgică va împărţi textul în cuvinte astfel: "a bc d". Dintre acestea, un singur cuvânt nu se găseşte în dicţionar - "d", iar lungimea acestuia este 1.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content