0259 - Eliminare 2: Difference between revisions

Latest revision as of 11:36, 27 December 2023

Cerinta[edit | edit source]

Se dau două şiruri, a şi b, cu n respectiv m elemente, numere naturale cu cel mult 9 cifre. Să se verifice dacă şirul b poate fi obţinut din şirul a, prin eliminarea unor elemente, fără a modifica ordinea inițială a elementelor.

Date de intrare[edit | edit source]

Fişierul de intrare eliminare2in.txt conţine pe prima linie numărul n; urmează n numere naturale, dispuse pe mai multe linii, reprezentând elementele şirului a. Următoarea linie conţine numărul m, şi urmează m numere naturale, dispuse pe mai multe linii, elementele şirului b.

Date de iesire[edit | edit source]

Fişierul de ieşire eliminare2out.txt va conţine pe prima linie valoarea 1, dacă putem obţine şirul b din a prin eliminarea unor valori, respectiv 0 în caz contrar.

Restrictii si precizari[edit | edit source]

1 ⩽ n,m ⩽ 100.000

Exemplul 1[edit | edit source]

eliminare2in.txt: 5; 1 6 3; 1 3; 3; 6 1 3
eliminare2out.txt: Datele introduse corespund restrictiilor impuse; 1

Exemplul 2[edit | edit source]

eliminare2in.txt: 3; -10 0 -328; -29104 263
eliminare2out.txt: Datele introduse nu corespund restrictiilor impuse

Rezolvare[edit | edit source]

<syntaxhighlight lang="python3" line="1"> def verificare_eliminate(a, b):

   i, j = 0, 0

   while i < len(a) and j < len(b):
       if a[i] == b[j]:
           j += 1
       i += 1

   return j == len(b)

Citirea datelor din fișierul de intrare

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

   n = int(f.readline())
   a = [int(f.readline()) for _ in range(n)]
   m = int(f.readline())
   b = [int(f.readline()) for _ in range(m)]

Verificarea dacă șirul b poate fi obținut din șirul a

rezultat = verificare_eliminate(a, b)

Scrierea rezultatului în fișierul de ieșire

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

   g.write(str(int(rezultat)))

</syntaxhighlight>

@@ Line 37: / Line 37: @@
 == Rezolvare ==
 <syntaxhighlight lang="python3" line="1">
-def poate_fi_obtinut(a, b):
+def verificare_eliminate(a, b):
-    n = len(a)
+     i, j = 0, 0
-    m = len(b)
-     i = j = 0
-     while i < n and j < m:
+     while i < len(a) and j < len(b):
-        # Dacă elementele sunt egale, trecem la următoarele elemente din ambii șiruri
          if a[i] == b[j]:
-            i += 1
              j += 1
-         else:
+         i += 1
-            # Dacă elementul din a nu este egal cu cel din b, trecem la următorul element din a
-            i += 1
-    # Dacă am parcurs toate elementele din b, atunci b poate fi obținut din a
+     return j == len(b)
-     return j == m
-def main():
+# Citirea datelor din fișierul de intrare
-    with open("eliminare2.txt", "r") as f_in:
+with open("eliminare2in.txt", "r") as f:
-        # Citim șirul a
+    n = int(f.readline())
-        n = int(f_in.readline())
+    a = [int(f.readline()) for _ in range(n)]
-        a = [int(f_in.readline()) for _ in range(n)]
+    m = int(f.readline())
+    b = [int(f.readline()) for _ in range(m)]
-        # Citim șirul b
+# Verificarea dacă șirul b poate fi obținut din șirul a
-        m = int(f_in.readline())
+rezultat = verificare_eliminate(a, b)
-        b = [int(f_in.readline()) for _ in range(m)]
-    # Verificăm dacă șirul b poate fi obținut din a
+# Scrierea rezultatului în fișierul de ieșire
-     rezultat = poate_fi_obtinut(a, b)
+with open("eliminare2out.txt", "w") as g:
+     g.write(str(int(rezultat)))
-    # Scriem rezultatul în fișierul de ieșire
-    with open("eliminare2.otxt", "w") as f_out:
-        f_out.write(str(int(rezultat)) + "\n")
-if __name__ == "__main__":
-    main()
 </syntaxhighlight>