Cerință
Se consideră șirul infinit inf="INFINFINFINF..."
.
Se dau două numere naturale n
și k
și un șir de caractere s
de lungime n
format doar din caracterele 'I'
, 'N'
și 'F'
.
Să se afle numărul minim de modificări ce trebuie realizate în șirul s
pentru a obține o subsecvență de lungime k
a șirului infinit inf
.
O modificare constă în schimbarea unui caracter din șirul s
cu un alt caracter din mulțimea {'I','N','F'}
.
De exemplu, în urma unei modificări a ultimului caracter, șirul "IIIFN"
devine "IIIFF"
.
Date de intrare
Fișierul de intrare inf.in
conține pe prima linie numerele n
și k
, iar pe a doua linie șirul s
format din n
caractere.
Date de ieșire
Fișierul de ieșire inf.out
va conține pe prima linie numărul de modificări necesare.
Restricții și precizări
2 ≤ n ≤ 1.500.000
1 ≤ k ≤ 500.000
k ≤ n
- Rezultatul poate fi
0
- O subsecvență de lungime
k
a șiruluis
reprezintă un șir format dink
elemente de pe poziții consecutive din șiruls
.
Exemplu 1:
inf.in
5 2 FNNNN
inf.out
1
Exemplu 2:
inf.in
5 5 NFFNI
inf.out
2
Explicație:
Exemplul 1: Numărul minim de modificări este 1. Înlocuind primul caracter cu 'I'
vom obține subsecvența de lungime 2: "IN"
.
Exemplul 2: Numărul minim de modificări este 2. Înlocuind al treilea caracter cu 'I'
și al cincilea caracter cu 'F'
vom obține subsecvența de lungime 5: "NFINF"
.