Fişierul intrare/ieşire:mesaj.in, mesaj.outSursăStelele Informaticii 2006, clasele 9-10
AutorMircea Bogdan PasoiAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.15 secLimită de memorie20096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content