Fişierul intrare/ieşire:raci.in, raci.outSursăInfoarena Monthly 2014, Runda 9
AutorAndrei Cristian LambruAdăugată demaritimCristian Lambru maritim
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inraci.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 .

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content