0259 - Eliminare 2

From Bitnami MediaWiki
Revision as of 11:34, 27 December 2023 by Mesarosdenisa (talk | contribs)

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