Cli

cli

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

Se dau $N$ cuvinte distincte formate din litere mici ale alfabetului englez $(a..z)$. Tu te afli în faţa unui terminal şi trebuie să tastezi cuvinte. Se pot folosi două tipuri de operaţii:
 
* adaugă ultimul caracter
* şterge ultimul caracter (numai dacă şirul curent este nevid)
 
Se mai dă un număr natural pozitiv $K$. Pentru fiecare $i$ de la $1$ la $K$ se cere să se aleagă $i$ cuvinte distincte din cele $N$ astfel încat numărul de operaţii folosite pentru a tasta toate cele $i$ cuvinte să fie minim. Un cuvânt se consideră tastat dacă la un anumit moment de timp şirul scris în terminal este identic cu acest cuvânt.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul cli.in conţine pe prima linie numerele naturale $N$ şi $K$, iar pe următoarele $N$ linii sunt cele $N$ cuvinte, câte unul pe linie.

Fişierul de intrare $cli.in$ ...

h2. Date de ieşire

Fişierul cli.out va conţine $K$ linii, pe linia $i$ aflându-se numărul minim de operaţii folosite pentru a tasta $i$ cuvinte distincte din cele $N$.

În fişierul de ieşire $cli.out$ ...

h2. Restricţii

* $1 ≤ K ≤ N$
* Suma lungimilor cuvintelor $≤ 1.000.000$
* Pentru $10$ puncte: $N ≤ 18$, suma lungimilor cuvintelor $≤ 100$.
* Pentru alte $20$ de puncte: $K ≤ 50$, suma lungimilor cuvintelor $≤ 500$.
* Pentru alte $20$ de puncte: $K ≤ 50$, suma lungimilor cuvintelor $≤ 10.000$.
* Pentru alte $30$ de puncte: $K ≤ 200$, suma lungimilor cuvintelor $≤ 100.000$.
* Pentru alte $20$ de puncte: $N * K ≤ 1.000.000$
* Linia de comanda începe şi trebuie să se termine cu şirul vid pentru fiecare $i$ de la $1$ la $K$.

* $... ≤ ... ≤ ...$

h2. Exemplu

table(example). |_. cli.in |_. cli.out |_. Explicaţie |
| 3 3
a
b
absc
|2
4
10
| Pentru i = 1, alegem cuvântul a.
Numărul de operaţii este 2:
vid -> a -> vid
Pentru i = 2 alegem cuvintele a şi b.
Avem nevoie de 4 operaţii pentru a le tasta:
vid -> a -> vid -> b -> vid
Pentru i = 3 alegem toate cele 3 cuvinte.
Numărul minim de operaţii este 10.
|

table(example). |_. cli.in |_. cli.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

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