| Fişierul intrare/ieşire: | mesaj.in, mesaj.out | Sursă | Stelele Informaticii 2006, clasele 9-10 |
| Autor | Mircea Bogdan Pasoi | Adăugată de |  Bogdan-Cristian Tataroiu •bogdan2412 |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20096 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Vezi solutiile trimise | Statistici
Mesaj
Zaharel ii trimite mesaje prietenei sale Eugenia folosind un sistem propriu de comunicatii (ca sa nu dea banii pe SMS-uri). Din pacate, sistemul lui Zaharel nu este complet eficient, iar uneori mesajul este distorsionat, mai exact este posibil sa apara caractere in plus in mesaj. Din fericire, vocabularul lui Zaharel este relativ limitat, iar Eugenia stie de profite de acest lucru: a facut o lista cu toate cele N cuvinte pe care le poate folosi Zaharel in cadrul mesajului. Sistemul lui Zaharel nu foloseste spatii pentru despartirea cuvintelor, dar Eugenia este destul de isteata sa-si dea seama intelesul mesajului, chiar si fara spatii.
Cerinta
Stiind lista de N cuvinte precum si mesajul final format din M caractere, aflati numarul minim de caractere pe care Eugenia trebuie sa le elimine din mesaj pentru ca acesta sa poate fi reprezentat ca o secventa de cuvinte din dictionar.
Date de intrare
Pe prima linie a fisierului mesaj.in se afla doua numere naturale N si M reprezentand numarul de cuvinte din lista si lungimea mesajului. Pe linia a doua se vor afla M caractere reprezentand mesajul. Urmatoarele N linii contin cate un cuvant din lista.
Date de iesire
Fisierul de iesire mesaj.out va contine o singura linie pe care se va afla numarul minim de caractere care trebuie sterse.
Restrictii
- 5 ≤ N ≤ 1 000
- 1 ≤ M ≤ 1 600
- Cuvintele din lista au lungimi cuprinse intre 1 si 20
- Mesajul si cuvintele sunt formate doar din litere mici din alfabetul englez {a, b, c ... z}
Exemplu
| mesaj.in | mesaj.out |
|---|---|
| 9 20 carmrcmddrcaddamroom car cdr cadar moo oom omo mr cam room | 4 |
Explicatie
carmrcmddrcaddamroom
Daca se elimina litere de culoare rosie, mesajul ramas va reprezenta urmatoare insiruire de cuvinte din lista:
car | mr | cdr | cadar | oom
