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 infIN.txt 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 infOUT.txt 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

• 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.

Exemplu 1:

infIN.txt

5 2
FNNNN

infOUT.txt

1

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".

Exemplu 2:

infIN.txt

1 5
NFFNI

infOUT.txt

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>