| Fişierul intrare/ieşire: | cli.in, cli.out | Sursă | ONI 2017, Baraj |
| Autor | Baltatu Andrei, Lucian Bicsi | Adăugată de |  Bogdan Ciobanu •bciobanu |
| Timp execuţie pe test | 0.4 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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.
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.
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.
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.
Exemplu
| 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. |
