Editing 0634 - Repetare

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

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 <code>input.txt</code> conține pe prima linie numărul <code>n</code> – numărul de elemente ale primului șir, iar pe a doua linie <code>n</code> numere naturale separate prin spații, reprezentând elementele primului șir. Linia a treia conține numărul <code>m</code> – numărul de elemente ale celui de-al doilea șir, iar a patra linie conține <code>m</code> numere naturale separate prin spații, reprezentând elementele șir șirului al doilea.

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

= Restricții și precizări =

* <code>1 ≤ n , m ≤ 1000</code>

== 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 <code>2 3 1 5 2 3 1 5 2 3 1 5</code> Prin eliminarea, în ordine a valorilor <code>3 1 2 2 5</code> 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>