Question

#259 Eliminare2

Cerinţa
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.in 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 ieşire
Fişierul de ieşire eliminare2.out 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.

Restricţii şi precizări
1 ≤ n,m ≤ 100.000



Exemplu
eliminare2.in

5
1 6 3
1 3
3
6 1 3
eliminare2.out

1

Answer 1

Răspuns:

#include<iostream>

#include<fstream>

using namespace std;

ifstream f("eliminare2.in");

ofstream g("eliminare2.out");

int a[100001],b[100001];

int main(){

int n;

   f>>n;

   for(int i = 0 ; i < n ;i ++){

    f>>a[i];

   }

   int m;

   f>>m;

   for(int i = 0 ; i < n ;i ++){

    f>>b[i];

   }

   int x = 0;

   for(int i = 0; i<n && x<m;i++){

       if(a[i] == b[x]){

           x++;

       }

   }

   if(x == m){

    g<<1;

    return 0;

   }

   else{

    g<<0;

   }

   return 0;

}

Explicație: