Editing 3134 - INF

== Cerinta ==

Se consideră șirul infinit <code>inf="INFINFINFINF..."</code>.

Se dau două numere naturale <code>n</code> și <code>k</code> și un șir de caractere <code>s</code> de lungime <code>n</code> format doar din caracterele <code>'I'</code> , <code>'N'</code> și <code>'F'</code>.

Să se afle numărul minim de modificări ce trebuie realizate în șirul <code>s</code> pentru a obține o subsecvență de lungime <code>k</code> a șirului infinit <code>inf</code>.

O modificare constă în schimbarea unui caracter din șirul <code>s</code> cu un alt caracter din mulțimea <code>{'I','N','F'}</code>.

De exemplu, în urma unei modificări a ultimului caracter, șirul <code>"IIIFN"</code> devine <code>"IIIFF"</code>.

= Date de intrare =
Fișierul de intrare <code>infIN.txt</code> conține pe prima linie numerele <code>n</code> și <code>k</code>, iar pe a doua linie șirul <code>s</code> format din <code>n</code> caractere.

= Date de ieșire =
Fișierul de ieșire <code>infOUT.txt</code> va conține pe prima linie numărul de modificări necesare. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

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

= Exemplu 1: =
<code>infIN.txt</code>
 5 2
 FNNNN
<code>infOUT.txt</code>
 1

== Explicație: ==
Exemplul 1: Numărul minim de modificări este 1. Înlocuind primul caracter cu <code>'I'</code> vom obține subsecvența de lungime 2: <code>"IN"</code>.

= Exemplu 2: =
<code>infIN.txt</code>
 1 5
 NFFNI
<code>infOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import deque

def next(ch):
    if ch == 'I':
        return 'N'
    if ch == 'N':
        return 'F'
    return 'I'

def check_constraints(n, k):
    if not (2 <= n <= 1_500_000 and 1 <= k <= 500_000 and k <= n):
        with open("infOUT.txt", "w") as outfile:
            outfile.write("Datele nu corespund restrictiilor impuse")
        return False
    return True

def main():
    with open("infIN.txt", "r") as infile:
        n, k = map(int, infile.readline().split())
        s = infile.readline().strip()

    if not check_constraints(n, k):
        return
    
    now = then = [s[i] for i in range(3)]  # Inițializăm now și then cu primele 3 caractere din șirul s
    result = [0, 0, 0]
    res = float('inf')  # Inițializăm res cu infinit
    q = deque()

    for i in range(1, n + 1):
        ch = s[i - 1]
        q.append(ch)
        for j in range(3):
            result[j] += (now[j] != ch)
            now[j] = next(now[j])
        
        if i >= k:
            if i > k:
                cnow = q.popleft()
                for j in range(3):
                    result[j] -= (then[j] != cnow)
                    then[j] = next(then[j])
            res = min(res, min(result))

    with open("infOUT.txt", "w") as outfile:
        if res != float('inf'):
            outfile.write(str(res))
        else:
            outfile.write("Datele nu corespund restrictiilor impuse")

if __name__ == "__main__":
    main()

</syntaxhighlight>