Editing 3134 - INF (section)

= 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>