Revizia anterioară Revizia următoare
| 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
Se da un numar N si N cuvinte formate doar din litere mici ale alfabetului englez.
Cerinţă
Sa se calculeze cel mai lung subsir de cuvinte din sirul initial ce respecta urmatoarele proprietati :
- Pentru orice i , 1 ≤ i ≤ M-1 , ultimul caracter al lui C i este egal cu primul caracter al lui C i+1
- Pentru orice i , 1 ≤ i ≤ M-1 , P i+1 - P i ≤ K , pentru un K dat
Unde M este lungimea noului sir rezultat , C i este cuvantul aflat pe pozitia i in noul sir si P i este pozitia pe care se afla cuvantul C i in sirul initial.
Date de intrare
Fişierul de intrare raci.in va contine pe prima linie doua valori N si K cu semnificatia din enunt.
Pe a doua linie din fisier se vor afla cele N cuvinte separate intre ele prin exact un spatiu.
Date de ieşire
În fişierul de ieşire raci.out se va afis o singura valoare reprezentand lungimea celui mai lung subsir de cuvinte care respecta cele doua proprietati specificate in enunt.
Restricţii
- 1 ≤ N ≤ 100 000
- 1 ≤ K ≤ N
- 2 ≤ lungimea oricarui cuvant ≤ 10
Exemplu
| raci.in | raci.out |
|---|---|
| 10 3 aa ab bc dd db be ff fg eh gi hj | 5 |
Explicaţie
Cel mai lung subsir este: aa ab bc dd db be ff fg eh gi hj .
