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

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