Latest revision as of 21:17, 22 March 2024

Cerinta[edit]

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[edit]

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[edit]

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[edit]

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:[edit]

infIN.txt

5 2
FNNNN

infOUT.txt

Explicație:[edit]

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:[edit]

infIN.txt

1 5
NFFNI

infOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare[edit]

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

@@ Line 1: / Line 1: @@
 == Cerinta ==
-Se consideră șirul infinit inf="INFINFINFINF...".
+Se consideră șirul infinit <code>inf="INFINFINFINF..."</code>.
-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'.
+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 s pentru a obține o subsecvență de lungime k a șirului infinit inf.
+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 s cu un alt caracter din mulțimea {'I','N','F'}.
+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 "IIIFN" devine "IIIFF".
+De exemplu, în urma unei modificări a ultimului caracter, șirul <code>"IIIFN"</code> devine <code>"IIIFF"</code>.
-== Date de intrare ==
+= 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.
-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 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".
-== Date de iesire ==
+= Restricții și precizări =
-Fișierul de ieșire inf.out va conține pe prima linie numărul de modificări necesare.
+* <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>.
-== Restrictii si precizari ==
+= Exemplu 1: =
+<code>infIN.txt</code>
+2
+ FNNNN
+<code>infOUT.txt</code>
-*2 ≤ n ≤ 1.500.000
+== Explicație: ==
-*1 ≤ k ≤ 500.000
+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>.
-*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 ==
+= Exemplu 2: =
+<code>infIN.txt</code>
-;infin.txt
+5
+ NFFNI
-:5 2
+<code>infOUT.txt</code>
+ Datele nu corespund restrictiilor impuse
-: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">
+from collections import deque
+def next(ch):
+    if ch == 'I':
+        return 'N'
+    if ch == 'N':
+        return 'F'
+    return 'I'
-def numar_minim_modificari(s, k):
+def check_constraints(n, k):
-     n = len(s)
+     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
-     # Calculăm numărul necesar de caractere 'I', 'N', 'F' pentru subsecvența dorită
+def main():
-    numar_i = k
+     with open("infIN.txt", "r") as infile:
-    numar_n = k - 1
+        n, k = map(int, infile.readline().split())
-    numar_f = k
+        s = infile.readline().strip()
-     # Numărăm caracterele existente în șirul dat
+     if not check_constraints(n, k):
-     numar_i_s = s.count('I')
+        return
-     numar_n_s = s.count('N')
-     numar_f_s = s.count('F')
+     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()
-     # Calculăm numărul minim de modificări
+     for i in range(1, n + 1):
-    modificari_necesare = max(0, numar_i - numar_i_s) + max(0, numar_n - numar_n_s) + max(0, numar_f - numar_f_s)
+        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))
-     return modificari_necesare
+     with open("infOUT.txt", "w") as outfile:
+        if res != float('inf'):
+            outfile.write(str(res))
+        else:
+            outfile.write("Datele nu corespund restrictiilor impuse")
-rezultat = numar_minim_modificari(sir, lungime_subsecventa)
+if __name__ == "__main__":
-print(f"Numărul minim de modificări necesare: {rezultat}")
+    main()
 </syntaxhighlight>