0259 - Eliminare 2

Cerinta

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

Fişierul de intrare eliminare2.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

Fişierul de ieşire eliminare2.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

• 1 ≤ n,m ≤ 100.000

Exemplul 1

Intrare

5

1 6 3

1 3

3

6 1 3

Iesire

Datele introduse corespund restrictiilor impuse

1

Exemplul 2

Intrare

3

-10 0 -328

-29104 263

Iesire

Datele introduse nu corespund restrictiilor impuse

Rezolvare

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

   n = len(a)
   m = len(b)
   i = j = 0

   while i < n and j < m:
       # Dacă elementele sunt egale, trecem la următoarele elemente din ambii șiruri
       if a[i] == b[j]:
           i += 1
           j += 1
       else:
           # 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 == m

def main():

   with open("eliminare2.txt", "r") as f_in:
       # Citim șirul a
       n = int(f_in.readline())
       a = [int(f_in.readline()) for _ in range(n)]

       # Citim șirul b
       m = int(f_in.readline())
       b = [int(f_in.readline()) for _ in range(m)]

   # Verificăm dacă șirul b poate fi obținut din a
   rezultat = poate_fi_obtinut(a, b)

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