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 dă un număr N si N cuvinte formate doar din litere mici ale alfabetului englez.
Cerinţă
Să se calculeze cel mai lung subsir de cuvinte din sirul iniţial ce respectă urmatoarele proprietăţi :
- 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 poziţia i in noul sir si P i este poziţia pe care se află cuvantul C i in sirul iniţial.
Date de intrare
Fişierul de intrare raci.in va conţine pe prima linie două valori N si K cu semnificaţia din enunţ.
Pe a doua linie din fisier se vor afla cele N cuvinte separate intre ele prin exact un spaţiu.
Date de ieşire
În fişierul de ieşire raci.out se va afisa o singură valoare reprezentand lungimea celui mai lung subsir de cuvinte care respectă cele două proprietăţi specificate in enunţ.
Restricţii
- 1 ≤ N ≤ 100 000
- 1 ≤ K ≤ N
- 2 ≤ lungimea oricărui 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 .
