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

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Repetare:

#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("repetare.in");
ofstream fout("repetare.out");

int n , m , a[1005], b[1005];

int main()
{
    fin >> n;
    for(int i = 1 ; i <= n ; i ++)
        fin >> a[i];
    fin >> m;
    for(int i = 1 ; i <= m ; ++ i)
        fin >> b[i];
    int cnt = 1;
    bool ok = true;
    int i = 1 , j = 1;
    while(j <= m && ok)
    {
        int ivechi = i;
        bool marit = false;
        while(i <= n && a[i] != b[j])
            i ++;
        if(i == n + 1)
        {
            i = 1;
            cnt ++;
            marit = true;
            while(i < ivechi && a[i] != b[j])
                i ++;
        }
        
        if(i == ivechi && marit)
        {
            // nu l-am gasi pe b[j] in a[], nu se poate 
            ok = false;
        }
        else
            i ++, j ++;
    }
    if(ok)
        fout << cnt;
    else
        fout << "IMPOSIBIL";
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #634 Repetare

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #634 Repetare de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #634 Repetare