Fişierul intrare/ieşire:zuma.in, zuma.outSursăONI 2018, clasele 11-12, ziua 2
AutorBogdan CiobanuAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test1 secLimită de memorie128000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Zuma

Se dă un șir de caractere de lungime N format din litere mari ale alfabetului englez și un număr întreg K.
Asupra șirului se poate aplica în mod repetat următoarea operație: se alege o subsecvență de lungime cel putin K având toate elementele egale și se elimină din șir. Evident că prima dată operația se aplică asupra șirului inițial și ulterior asupra șirului obținut din aplicarea operației anterioare. Operația se aplică până când șirul devine șirul vid (de lungime 0) sau șirul nu mai conține subsecvențe de lungime cel puțin K cu toate elemente egale.

Cerință

Cunoscând N, K și șirul de caractere, să se determine care este lungimea minimă la care poate fi redus șirul după aplicarea operațiilor într-un mod convenabil.

Date de intrare

Fișierul de intrare zuma.in conține pe prima linie numerele N și K separate prin spațiu și pe a doua linie șirul de caractere format din N litere mari.

Date de ieșire

În fișierul de ieșire zuma.out trebuie să afișați un singur număr natural reprezentând lungimea minimă pe care o poate avea șirul după aplicarea în mod convenabil a operațiilor.

Restricții

  • 1 ≤ K ≤ N ≤ 500
  • Pentru teste în valoare de 10 puncte 25 ≤ K ≤ N ≤ 100
  • Pentru alte teste în valoare de 10 puncte K = 2
  • Pentru alte teste în valoare de 10 puncte numărul de caractere distincte din șir este 2
  • Pentru alte teste în valoare de 15 puncte 1 ≤ N ≤ 50
  • Pentru alte teste în valoare de 35 puncte 1 ≤ N ≤ 200

Exemplu

zuma.inzuma.out
10 3
AAABBBCCCA
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?