0634 - Repetare

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 input.txt 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 output.txt 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

Exemplul 1

input.txt:

4

2 3 1 5

7

2 5 3 1 5 3 1

output.txt:

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.

Exemplul 2

input.txt:

9999999

2 3 1 5

7

2 5 3 1 5 3 1

Output:

Constrangeri neindeplinite

Rezolvare

<syntaxhighlight lang="python3" line="1"> def ver(n,m):

   if not(1<=n<=1000):
       print("Constrangeri neindeplinite")
       exit()
   if not(1<=m<=1000):
       print("Constrangeri neindeplinite")
       exit()

with open("input.txt", 'r') as fin, open("output.txt", 'w') as fout:

   n = int(fin.readline())
   ver(n,10)
   a = list(map(int, fin.readline().split()))
   m = int(fin.readline())
   ver(10,m)
   b = list(map(int, fin.readline().split()))

   cnt = 1
   ok = True
   i, j = 0, 0

   while j < m and ok:
       ivechi = i
       marit = False
       while i < n and a[i] != b[j]:
           i += 1
       if i == n:
           i = 0
           cnt += 1
           marit = True
           while i < ivechi and a[i] != b[j]:
               i += 1
       
       if i == ivechi and marit:
           # nu l-am gasit pe b[j] in a[], nu se poate
           ok = False
       else:
           i += 1
           j += 1
   
   if ok:
       fout.write(str(cnt))
   else:
       fout.write("IMPOSIBIL")

</syntaxhighlight>