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

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

• 1 ⩽ n,m ⩽ 100.000

Exemplul 1

eliminare2in.txt

5

1 6 3

1 3

3

6 1 3

eliminare2out.txt

Datele introduse corespund restrictiilor impuse

1

Exemplul 2

eliminare2in.txt

3

-10 0 -328

-29104 263

eliminare2out.txt

Datele introduse nu corespund restrictiilor impuse

Rezolvare

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

1. 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)]

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

rezultat = verificare_eliminate(a, b)

1. Scrierea rezultatului în fișierul de ieșire

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

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

</syntaxhighlight>