| Fişierul intrare/ieşire: | raci.in, raci.out | Sursă | Infoarena Monthly 2014, Runda 9 |
| Autor | Andrei Cristian Lambru | Adăugată de |  Cristian Lambru •maritim |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Raci
Antoniei îi plac foarte mult crustaceele. Fiindcă lui Antonio îi este imposibil să îi ofere acesteia un rac drept cadou, s-a gândit să numească această problemă... Raci
Se dă un număr N şi N cuvinte formate doar din litere mici ale alfabetului englez.
Cerinţă
Să se calculeze cel mai lung subşir de cuvinte din şirul iniţial ce respectă următoarele proprietăţi :
- Pentru orice i , 1 ≤ i ≤ M-1 , ultimul caracter al lui Ci este egal cu primul caracter al lui Ci+1
- Pentru orice i , 1 ≤ i ≤ M-1 , Pi+1 - Pi ≤ K , pentru un K dat
Unde M este lungimea noului şir rezultat , Ci este cuvântul aflat pe poziţia i în noul şir şi Pi este poziţia pe care se află cuvântul Ci în şirul iniţial.
Date de intrare
Fişierul de intrare raci.in va conţine pe prima linie două valori N şi K cu semnificaţia din enunţ.
Pe a doua linie din fişier se vor afla cele N cuvinte separate între ele prin exact un spaţiu.
Date de ieşire
În fişierul de ieşire raci.out se va afişa o singură valoare reprezentând lungimea celui mai lung subşir de cuvinte care respectă cele două proprietăţi specificate în enunţ.
Restricţii
- 1 ≤ N ≤ 500 000
- 1 ≤ K ≤ N
- 2 ≤ lungimea oricărui cuvânt ≤ 10
Exemplu
| raci.in | raci.out |
|---|---|
| 11 3 aa ab bc dd db be ff fg eh gi hj | 5 |
Explicaţie
Cel mai lung subşir este: aa ab bc dd db be ff fg eh gi hj .
