0262 - Intervale 1: Difference between revisions

Latest revision as of 12:16, 29 December 2023

Cerinta[edit | edit source]

Se dă un șir de n numere reale, în ordine strict crescătoare. Să se determine un număr natural x, cu proprietatea că în orice interval deschis având drept capete oricare două valori din șir se află cel puțin x numere întregi.

Date de intrare[edit | edit source]

Fişierul de intrare intervale1in.txt conţine pe prima linie numărul n; urmează n numere reale, în ordine strict crescătoare, separate prin spaţii, reprezentând elementele şirului, ce pot fi dispuse pe mai multe linii.

Date de iesire[edit | edit source]

Fişierul de ieşire intervale1out.txt va conţine pe prima linie numărul x.

Restrictii si precizari[edit | edit source]

1 ⩽ n ⩽ 100.000
numerele reale din fișierul de intrare au valoarea absolută mai mică decât 100.000.000

Exemplul 1[edit | edit source]

intervale1in.txt: 6; 3.5 5.1 9.2 16 20.33 100
intervale1out.txt: Datele introduse corespund restrictiilor impuse; 2

Exemplul 2[edit | edit source]

intervale1in.out: 6; 100 20.33 16 9.2 5.1 3.5

Datele introduse nu corespund restrictiilor impuse

Rezolvare[edit | edit source]

<syntaxhighlight lang="python3" line="1"> def gaseste_x(șir):

   # Inițializare x cu o valoare mare
   x = float("inf")

   # Parcurgere șir și actualizare x
   for i in range(1, len(șir)):
       distanța = int(șir[i] - șir[i-1])
       x = min(x, distanța)

   return x + 1  # x este minimul număr natural care îndeplinește condiția

Citirea datelor din fișierul de intrare

with open("intervale1in.txt", "r") as f:

   n = int(f.readline())
   șir = [float(f.readline()) for _ in range(n)]

Calculul valorii x

rezultat = gaseste_x(șir)

Scrierea rezultatului în fișierul de ieșire

with open("intervale1out.txt", "w") as g:

   g.write(str(rezultat))

Verificare restrictii

assert 1 <= n <= 100000 for i in range(n):

   assert abs(șir[i]) < 100000000

</syntaxhighlight>

@@ Line 34: / Line 34: @@
 == Rezolvare ==
 <syntaxhighlight lang="python3" line="1">
-def cmmdc(a, b):
-    while b:
-        a, b = b, a % b
-    return a
 def gaseste_x(șir):
-     diferențe = [șir[i + 1] - șir[i] for i in range(len(șir) - 1)]
+     # Inițializare x cu o valoare mare
+     x = float("inf")
-    x = diferențe[0]
-     for diferența in diferențe[1:]:
-        x = cmmdc(x, diferența)
-     return x
+     # Parcurgere șir și actualizare x
+    for i in range(1, len(șir)):
+        distanța = int(șir[i] - șir[i-1])
+        x = min(x, distanța)
-def main():
+     return x + 1  # x este minimul număr natural care îndeplinește condiția
-     with open("intervale1.txt", "r") as f_in:
-        # Citim lungimea șirului
-        n = int(f_in.readline())
-        # Citim șirul de numere reale
+# Citirea datelor din fișierul de intrare
-        sir = [float(f_in.readline()) for _ in range(n)]
+with open("intervale1in.txt", "r") as f:
+    n = int(f.readline())
+    șir = [float(f.readline()) for _ in range(n)]
-    # Calculăm x folosind diferențele dintre elemente
+# Calculul valorii x
-    rezultat = gaseste_x(sir)
+rezultat = gaseste_x(șir)
-    # Scriem rezultatul în fișierul de ieșire
+# Scrierea rezultatului în fișierul de ieșire
-    with open("intervale1.txt", "w") as f_out:
+with open("intervale1out.txt", "w") as g:
-        f_out.write(str(rezultat) + "\n")
+    g.write(str(rezultat))
-if __name__ == "__main__":
+# Verificare restrictii
-     main()
+assert 1 <= n <= 100000
+for i in range(n):
+     assert abs(șir[i]) < 100000000
 </syntaxhighlight>