2198 – Elimin Prime: Difference between revisions

Latest revision as of 15:01, 3 January 2024

Se consideră un șir de n numere întregi, cu n număr natural nenul. Se elimină primul element din șir și toate elementele șirului aflate pe poziții care reprezintă numere prime, în ordinea crescătoare a pozițiilor. Operația de eliminare se repetă cu elementele rămase în șir, repoziționate după eliminarea celorlalte, până când este eliminat și ultimul element rămas.

Cerinţa[edit | edit source]

Să se scrie un program care afișează elementele șirului inițial, în ordinea în care au fost eliminate conform algoritmului descris mai sus.

Date de intrare[edit | edit source]

Fișierul de intrare elimin_primein.txt conține pe prima linie numărul n, iar pe a doua linie n numere întregi separate prin spații.

Date de ieșire[edit | edit source]

Fișierul de ieșire elimin_primeout.txt va conține pe prima linie, separate prin spațiu, numerele din fișierul de intrare în ordinea eliminării acestora.

Restricţii şi precizări[edit | edit source]

1 ⩽ n ⩽ 100.000
numerele de pe a doua linie a fișierului de intrare sun cuprinse în intervalul [-1.000.000.000, 1.000.000.000]
elementele șirului sunt indexate de la 1 la n.

Exemplul 1[edit | edit source]

elimin_primein.txt

10 
1 2 3 4 5 6 7 8 9 10

elimin_primeout.txt

Datele de intrare corespund restrictiilor impuse
1 2 3 5 7 4 6 8 10 9

Exemplu 2[edit | edit source]

elimin_primein.txt

100001
1 2 3 4 5 6 7 8 9 10 ... 1000001

elimin_primeout.txt

Datele de intrare nu corespund restrictiilor impuse

Atentie![edit | edit source]

Programele vor folosi doar instrucțiunile de bază ale limbajului de programare ales, inclusiv cele de intrare/ieșire, dar nu și alte funcții din biblioteci specializate (algorithm, string,…).

Rezolvare[edit | edit source]

<syntaxhighlight lang="python" line> def main():

   with open('elimin_primein.txt', 'r') as fin, open('elimin_primeout.txt', 'w') as fout:
       n = int(fin.readline().strip())
       if n < 1 or n > 100000:
           fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
           return
       numbers = list(map(int, fin.readline().strip().split()))
       if any(x < -1000000000 or x > 1000000000 for x in numbers):
           fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
           return
       fout.write("Datele de intrare corespund restrictiilor impuse\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>

@@ Line 21: / Line 21: @@
 == Exemplu 2 ==
 ; elimin_primein.txt
-3 4 5 6 7 8 9 10 4 23 16 -7 89 115 23 11 15 2 -8 -9 21 0 75 23 32 -1 4 5 ...
+2 3 4 5 6 7 8 9 10 ... 1000001
 ; elimin_primeout.txt
   Datele de intrare nu corespund restrictiilor impuse
@@ Line 31: / Line 31: @@
 == Rezolvare ==
 <syntaxhighlight lang="python" line>
-def este_prim(n):
-    if n < 2:
-        return False
-    if n == 2:
-        return True
-    if n % 2 == 0:
-        return False
-    p = 3
-    while p * p <= n:
-        if n % p == 0:
-            return False
-        p += 2
-    return True
 def main():
-     sir = list(map(int, input().split()))
+     with open('elimin_primein.txt', 'r') as fin, open('elimin_primeout.txt', 'w') as fout:
+        n = int(fin.readline().strip())
-    if len(sir) > 100000:
+        if n < 1 or n > 100000:
-        print("Datele de intrare nu corespund restrictiilor impuse")
+            fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
-        return
+            return
+        numbers = list(map(int, fin.readline().strip().split()))
-    eliminat = []
+         if any(x < -1000000000 or x > 1000000000 for x in numbers):
+             fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
-    while sir:
+             return
-        eliminat.append(sir.pop(0))
+        fout.write("Datele de intrare corespund restrictiilor impuse\n")
-         i = 1
-        while i < len(sir):
-             if este_prim(i+1):
-                eliminat.append(sir.pop(i))
-             else:
-                i += 1
-    print("Datele de intrare corespund restrictiilor impuse")
-    print(' '.join(map(str, eliminat)))