3134 - INF

Cerinta

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 iesire

Fișierul de ieșire inf.out va conține pe prima linie numărul de modificări necesare.

Restrictii si precizari

2 ≤ n ≤ 1.500.000
1 ≤ k ≤ 500.000
k ≤ n
Rezultatul poate fi 0
O subsecvență de lungime k a șirului s reprezintă un șir format din k elemente de pe poziții consecutive din șirul s.

Exemplul 1

infin.txt

5 2

FNNNN

infout.txt

Datele introduse corespund restrictiilor impuse.

1

Exemplul 2

infin.txt

10 12

FFNNI

infout.txt

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

def numar_minim_modificari(s, k):

   n = len(s)

   # Calculăm numărul necesar de caractere 'I', 'N', 'F' pentru subsecvența dorită
   numar_i = k
   numar_n = k - 1
   numar_f = k

   # Numărăm caracterele existente în șirul dat
   numar_i_s = s.count('I')
   numar_n_s = s.count('N')
   numar_f_s = s.count('F')

   # Calculăm numărul minim de modificări
   modificari_necesare = max(0, numar_i - numar_i_s) + max(0, numar_n - numar_n_s) + max(0, numar_f - numar_f_s)

   return modificari_necesare

rezultat = numar_minim_modificari(sir, lungime_subsecventa) print(f"Numărul minim de modificări necesare: {rezultat}")

</syntaxhighlight>