mesaj

Mesaj

== include(page="template/taskheader" task_id="mesaj") ==

Poveste si cerinta...

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

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

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

h2. 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}$
 

h2. Exemplu
table(example). |_. mesaj.in |_. mesaj.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 9 20
carmrcmddrcaddamroom
car
cdr
cadar
moo
oom
omo
mr
cam
room
| 4

|
h3. Explicatie

...

$carmrc{%{color:red}md%}drcad{%{color:red}d%}a{%{color:red}m%}room$
Daca se elimina litere de culoare rosie, mesajul ramas va reprezenta urmatoare insiruire de cuvinte din lista:
$car | mr | cdr | cadar | oom$

== include(page="template/taskfooter" task_id="mesaj") ==

1681