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

2 0 1

Exemplul 2:

Intrare

5

3 1 4 2 5

4 5 1 3 2

Ieșire

3 2 0 0 0

Exemplul 3:

Intrare

6

6 5 4 3 2 1

6 5 3 4 2 1

Ieșire

1 1 2 0 1 1

Rezolvare

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

def muta_carti(n, a, b):

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

   # Parcurgem array-ul a și pentru fiecare element a[i], setăm poz[a[i]] la i + 1
   for i in range(n):
       poz[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(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[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__":

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

   # 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))

</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.