fbpx

Problema #634 – Repetare – Rezolvari PBInfo

de Mihai-Alexandru

Cerința

Gigel are un șir cu n elemente, numere naturale. Plictisit, el construiește un nou șir, prin scrierea repetată a valorilor șirului dat. De exemplu, dacă șirul inițial este (2 3 1 5), scriindu-l de 3 ori se obține șirul: (2 3 1 5 2 3 1 5 2 3 1 5).

Maleficul Costel elimină sau chiar schimbă unele valori din șirul al doilea. Acum Gigel vă pune la dispoziție două șiruri de numere naturale și roagă să stabiliți dacă al doilea șir poate obține prin scrierea repetată a primului șir și eliminarea unor elemente iar în caz afirmativ care este numărul minim de repetări ale primului șir prin care se poate obține șirul al doilea.

Date de intrare

Fișierul de intrare repetare.in conține pe prima linie numărul n – numărul de elemente ale primului șir, iar pe a doua linie n numere naturale separate prin spații, reprezentând elementele primului șir. Linia a treia conține numărul m – numărul de elemente ale celui de-al doilea șir, iar a patra linie conține m numere naturale separate prin spații, reprezentând elementele șir șirului al doilea.

Date de ieșire

Fișierul de ieșire repetare.out va conține pe prima linie numărul C, reprezentând numărul minim de repetări ale primului șir prin care se poate obține ale doilea șir, sau valoarea IMPOSIBIL dacă al doilea șir nu poate fi obținut prin scrierea repetată a primului șir și eliminarea unor valor..

Restricții și precizări

  • 1 ≤ n , m ≤ 1000
  • elementele celor două șiruri vor fi numere naturale mai mici decât 1 000 000 000

Exemplu

repetare.in

4
2 3 1 5
7
2 5 3 1 5 3 1 

repetare.out

3

Explicație

Prin repetarea de trei ori a primului șir se obține șirul 2 3 1 5 2 3 1 5 2 3 1 5 Prin eliminarea, în ordine a valorilor 3 1 2 2 5 se obține șirul al doilea. Repetând șirul dat de mai puțin de trei ori, oricum a elimina valori din șirul rezultat nu se poate obține al doilea șir.

#include <bits/stdc++.h>
using namespace std;
ifstream cin("repetare.in");
ofstream cout("repetare.out");
int main()
{
    int n , m , a[1000] , b[1000] , ok = 0;
    cin >> n;
    for(int i = 0 ; i < n ; ++i)
        cin >> a[i];
    cin >> m;
    for(int i = 0 ; i < m ; ++i)
        cin >> b[i];
    for(int i = 0 ; i < m ; ++i)
    {
        int cnt = 0;
        for(int j = 0 ; j < n ; ++j)
            if(b[i]!=a[j]) cnt++;
        if(cnt == n)
        ok = 1;
    }
    if(ok == 0)
    {
        int k = 0 , i = 0 , cnt = 0;
        while(m > 1)
        {
            if(b[i]==a[k])
                i++ , m--;
            k++;
            if(k==n) cnt++ , k = 0;
        }
        cout << cnt+1;
    }
    else cout << "IMPOSIBIL";
    return 0;
}
Comentarii

S-ar putea sa iti placa