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 \( {a}_{1} \), următoarea \( {a}_{2} \) și așa mai departe. Cartea de la bază are indicele n (\( {a}_{n} \)). 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 \( {b}_{i} \) î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 \( {a}_{1},{a}_{2},…,{a}_{n} \). A treia linie va conține alte n numere întregi, anume \( {b}_{1},{b}_{2},…,{b}_{n} \).
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 ≤\( {a}_{1},{a}_{2},…,{a}_{n},{b}_{1},{b}_{2},…,{b}_{n} \)≤ n ≤ 200.000;- Numerele \( {a}_{1},{a}_{2},…,{a}_{n} \) sunt distincte între ele;
- Numerele \( {b}_{1},{b}_{2},…,{b}_{n} \) 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
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.
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 books:
#include <iostream>
using namespace std;
int main()
{
int n, v[200001], currpos = 0, i, j, x;
bool stiva[200001]{};
cin >> n;
for(i = 0; i < n; ++i)
cin >> v[i];
for(i = 0; i < n; ++i)
{
cin >> x; j = currpos;
if(!stiva[x])
{
j = currpos;
while(v[j] != x) { stiva[v[j]] = true; ++j; }
cout << j - currpos + 1;
currpos = j + 1;
}
else cout.put('0');
cout.put(' ');
}
return 0;
}
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 
.
Rezolvarea problemei #2650 books
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2650 books 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!