0184 - Interval 1: Difference between revisions

Revision as of 13:06, 27 December 2023

Cerinta

Se dă un şir de n' numere întregi şi un număr k. Să se determine intervalul [a,b] de lungime minimă care conţine cel puţin k elemente din sir.

Date de intrare

Fişierul de intrare interval1i.txt conţine pe prima linie numerele n şi k, iar pe următoarele linii n numere întregi separate prin spaţii, reprezentând elementele şirului.

Date de iesire

Fişierul de ieşire interval1out.txt va conţine pe prima linie două numere a şi b, separate printr-un spaţiu, cu semnificaţia de mai sus.

Restrictii si precizari

1 ⩽ k ⩽ n ⩽ 1000
elementele şirului aparţin intervalului [-1000,1000] şi pot fi dispuse în fişierul de intrare pe mai multe linii
dacă există mai multe intervale [a,b] de lungime minimă care conţin cel puţin k elemente din sir se va alege acela pentru care a este minim
a ≤ b

Exemplul 1

interval1in.txt: 10 3; 11 9 3 2 8 11 9 10 15 13
interval1out.txt: Datele introduse corespund restrictiilor impuse; 8 9

Exemplul 2

interval1in.txt: 4 2; 20,5,100,75.2

Datele introduse nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def gaseste_interval(n, k, sir):

   index_start = 0
   index_end = k - 1
   sir.sort()

   lungime_minima = sir[index_end] - sir[index_start]
   interval_minim = (sir[index_start], sir[index_end])

   for i in range(1, n - k + 1):
       lungime_curenta = sir[i + k - 1] - sir[i]
       if lungime_curenta < lungime_minima:
           lungime_minima = lungime_curenta
           index_start = i
           index_end = i + k - 1
           interval_minim = (sir[index_start], sir[index_end])

   return interval_minim

Citire din fișierul de intrare

with open('interval1i.txt', 'r') as file:

   n, k = map(int, file.readline().split())
   sir = []
   for _ in range(n):
       sir.extend(map(int, file.readline().split()))

Apelare funcție

rezultat = gaseste_interval(n, k, sir)

Scriere în fișierul de ieșire

with open('interval1out.txt', 'w') as file:

   file.write(f"{rezultat[0]} {rezultat[1]}")

</syntaxhighlight>

Explicatie

Intervalul [8,9] conţine 3 elemente ale şirului – 8 9 9 şi are lungimea minimă. Există încă un interval cu aceeaşi lungime care conţine 3 elemente din şir – [9,10] elemente dar 8<9.

@@ Line 36: / Line 36: @@
 == Rezolvare ==
 <syntaxhighlight lang="python3" line="1">
-def gaseste_interval_minim(sir, n, k):
+def gaseste_interval(n, k, sir):
-     a = b = 0  # Pointer-ele pentru intervalul minim [a, b]
+     index_start = 0
-     numere_gasite = 0  # Numărul de elemente găsite în interval
+    index_end = k - 1
+     sir.sort()
-     # Inițializează un dicționar pentru a număra de câte ori apare fiecare element în interval
+     lungime_minima = sir[index_end] - sir[index_start]
-     frecventa_elemente = {}
+     interval_minim = (sir[index_start], sir[index_end])
-     while b < n:
+     for i in range(1, n - k + 1):
-         # Extinde intervalul spre dreapta
+         lungime_curenta = sir[i + k - 1] - sir[i]
-        frecventa_elemente[sir[b]] = frecventa_elemente.get(sir[b], 0) + 1
+         if lungime_curenta < lungime_minima:
-         if frecventa_elemente[sir[b]] == 1:
+            lungime_minima = lungime_curenta
-             numere_gasite += 1
+            index_start = i
+            index_end = i + k - 1
+             interval_minim = (sir[index_start], sir[index_end])
-        # Dacă am găsit cel puțin k elemente, încercăm să restrângem intervalul spre stânga
+    return interval_minim
-        while numere_gasite >= k:
-            # Verificăm dacă este intervalul minim și actualizăm rezultatul
-            if b - a < b_min - a_min:
-                a_min, b_min = a, b
-            # Încercăm să restrângem intervalul spre stânga
+# Citire din fișierul de intrare
-            frecventa_elemente[sir[a]] -= 1
+with open('interval1i.txt', 'r') as file:
-            if frecventa_elemente[sir[a]] == 0:
+    n, k = map(int, file.readline().split())
-                numere_gasite -= 1
+    sir = []
-            a += 1
+    for _ in range(n):
+        sir.extend(map(int, file.readline().split()))
-        # Extinde intervalul spre dreapta
+# Apelare funcție
-        b += 1
+rezultat = gaseste_interval(n, k, sir)
-     return a_min, b_min
+# Scriere în fișierul de ieșire
+with open('interval1out.txt', 'w') as file:
+     file.write(f"{rezultat[0]} {rezultat[1]}")
-def main():
-    with open("interval1.txt", "r") as f_in:
-        # Citim numărul de elemente și k
-        n, k = map(int, f_in.readline().split())
-        # Citim șirul de numere
-        sir = list(map(int, f_in.readline().split()))
-    # Găsim intervalul minim
-    a, b = gaseste_interval_minim(sir, n, k)
-    # Scriem rezultatul în fișierul de ieșire
-    with open("interval1.txt", "w") as f_out:
-        f_out.write(f"{a} {b}\n")
-if __name__ == "__main__":
-    main()
 </syntaxhighlight>