Editing 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 ==
<syntaxhighlight lang="python3" line="1">

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>