2650 - books

Eroul nostru, Căldărușe, are un număr n de cărți pe care le are aranjate una peste cealaltă (sub forma unui stack). Cartea din vârf are valoarea a1, următoarea a2 și așa mai departe. Cartea de la bază are indicele n (an). Toate numerele sunt distincte.

Căldărușe vrea să mute toate cărțile în ghiozdanul lui în exact n pași. În timpul pasului de ordin i, el vrea să mute cartea cu numărul bi în ghiozdan. Dacă această carte se află în stack, el o ia atât pe ea, cât și toate cărțile situate deasupra acesteia și le pune în ghiozdan; în caz contrar, el nu va face nimic și va trece la următorul pas. De exemplu, dacă în stack cărțile sunt aranjate în ordinea [1, 2, 3] (cartea cu numărul 1 este aflată în vârf) și pașii prin care Căldărușe trece sunt, în această ordine, [2, 1, 3], atunci în cadrul primului pas el va muta două cărți (1 și 2), în cadrul celui de-al doilea pas nu va face nimic (din moment ce cartea cu numărul 1 este deja în ghiozdan) și în cadrul ultimului pas va muta o singură carte (cartea cu numărul 3).

Cerința

Ajutați-l pe Căldărușe! Spuneți-i voi numărul de cărți pe care le va pune în ghiozdan în timpul fiecărui pas.

Date de intrare

Prima linie va conține numărul n, cu semnificația din enunț. Următoarea linie va conține n numere întregi, anume a1,a2,…,an. A treia linie va conține alte n numere întregi, anume b1,b2,…,bn.

Date de ieșire

Programul va afișa pe ecran n numere întregi. Elementul de ordine i ar trebui să fie egal cu numărul de cărți pe care Căldărușe le mută în ghiozdanul său în timpul pasului i.

Restricții și precizări

• 1 ≤ a1,a2,…,an,b1,b2,…,bn ≤ n ≤ 200.000;
• Numerele a1,a2,…,an sunt distincte între ele;
• Numerele b1,b2,…,bn sunt distincte între ele.

Exemplul 1:

Intrare

3

1 2 3

2 1 3

Ieșire

Datele de intrare corespund restrictiilor impuse.

2 0 1

Exemplul 2:

Intrare

5

3 1 4 2 5

4 5 1 3 2

Ieșire

Datele de intrare corespund restrictiilor impuse.

3 2 0 0 0

Exemplul 3:

Intrare

6

6 5 4 3 2 1

6 5 3 4 2 1

Ieșire

Datele de intrare corespund restrictiilor impuse.

1 1 2 0 1 1

Exemplul 4:

Intrare

0

Ieșire

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line="1" start="1">

def verificare_restrictii(nr_n):

   # Functia de verificare a datelor de intrare
   if 1 <= nr_n <= 200000:
       return True
   else:
       return False

def muta_carti(nr_n, nr_a, nr_b):

   # Verificam daca numerele sunt distincte
   if len(set(a)) != nr_n or len(set(nr_b)) != nr_n:
       return "Numerele nu sunt distincte între ele."

   # Creăm un array poz cu lungimea n + 1
   poz = [0] * (nr_n + 1)

   # Parcurgem array-ul a și pentru fiecare element a[i], setăm poz[a[i]] la i + 1
   for i in range(nr_n):
       poz[nr_a[i]] = i + 1

   # Inițializăm rezultatul ca un array gol
   rez = []

   # Inițializăm max_poz la 0
   max_poz = 0

   # Parcurgem array-ul b
   for i in range(nr_n):
       # Dacă poz[b[i]] este mai mare decât max_poz, adăugăm diferența la rezultat și actualizăm max_poz
       if poz[nr_b[i]] > max_poz:
           rez.append(poz[b[i]] - max_poz)
           max_poz = poz[b[i]]
       else:
           # Altfel, adăugăm 0 la rezultat
           rez.append(0)

   # Returnăm rezultatul
   return rez

if __name__ == "__main__":

   try:
       # Introdu datele de intrare manual
       n = int(input("Introdu numărul de cărți: "))

       # Verificam daca datele de intrare corespund restrictiilor
       if verificare_restrictii(n):
           print("Datele de intrare corespund restrictiilor impuse.")

           # Convertim string-ul de intrare într-un array de numere întregi
           a = list(map(int, input("Introdu ordinea cărților în stack: ").split()))

           # Convertim string-ul de intrare într-un array de numere întregi
           b = list(map(int, input("Introdu ordinea în care vrei să muți cărțile: ").split()))

           # Afișează rezultatul
           print(muta_carti(n, a, b))
       else:
           print("Datele de intrare nu corespund restrictiilor impuse.")
   except ValueError:
       print("Datele de intrare nu corespund restrictiilor impuse.")
   except IndexError:
       print("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>

Explicație

Primul exemplu este descris în enunț. În cel de-al doilea exemplu, în timpul primului pas, Căldărușe va muta cărțile [3, 1, 4]. După aceea, numai cărțile 2 și 5 vor rămâne în stack (cartea 2 fiind deasupra cărții 5). În timpul celui de-al doilea pas, Căldărușe va lua și cărțile 2 și 5. După aceea, stackul rămâne gol, și deci în timpul următorilor pași, Căldărușe nu va mai muta nicio carte.