Fişierul intrare/ieşire:cli.in, cli.outSursăONI 2017, Baraj
AutorBaltatu Andrei, Lucian BicsiAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test0.8 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/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.incli.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?