Fişierul intrare/ieşire:	queue.in, queue.out	Sursă	Algoritmiada 2013, Runda 2
Autor	Serban Andrei Stan	Adăugată de	Mihai Gheorghe •GheorgheMihai
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Queue

Vrem sa simulam o Coada folosind 2 Stive.

O coada este o structura de date ce suporta urmatoarele operatii:

• push_back(X) - elementul X se adauga in capatul dreapta al cozii
• pop_front() - se sterge un element din capatul stanga al cozii

O stiva este o structura de date ce suporta urmatoarele operatii:

• push(S,X) - elementul X se adauga in capul stivei S
• pop(S) - se sterge un element din capul stivei S

Dupa efectuarea unei operatii de pop, valoarea dintr-o stiva va fi amplasata in variabila WR. Spre exemplu, ca sa mutam capul stivei 1 in stiva 2 trebuie sa efectuam urmatorul set de operatii: pop(1) push(2,WR). Capul stivei 1 va ajunge in variabila WR, si putem folosi aceasta variabila pentru a introduce valoarea in stiva 2.

Date de intrare

Fişierul de intrare queue.in va contine pe prima linie numerul natural N reprezentand numarul total de operatii efectuate pe Coada. Pe fiecare dintre urmatoarele N linii se va afla cate o operatie pe Coada, din cele 2 descrise in enunt.

Date de ieşire

În fişierul de ieşire queue.out trebuie sa existe N linii. Fiecare linie din fisierul de output trebuie sa inceapa cu indicele operatiei din input careia sirul de operatii de pe linia curenta ii corespunde, urmat de caracterele ":"," ". Pe linia i trebuie sa existe o serie de operatii valide efectuate pe stive, separate prin cate un spatiu. In cazul in care operatia din input este de tip push, pentru a introduce valoarea din input in variabila WR trebuie folosita instructiunea read(WR). In cazul in care operatia din input este de tip pop, pentru a afisa variabila WR trebuie folosita instructiunea write(WR).

Restricţii

• 1 ≤ N ≤ 30 000
• O operatie de push efectuata pe una dintre stive se considera valida daca valoare folosita se afla in WR.
• Toate valorile folosite in operatiile de push_back vor fi distincte.
• Toate valorile folosite in operatiile de push_back vor fi numere naturale ≤ 10⁶.
• Pe fiecare linie a fisierului de output puteti afisa maximum 500 000 caractere, altfel outputul se va considera invalid.
• Pentru orice operatie de tip push_back(x) trebuie sa se faca fix o operatie de tip read(x)
• Pentru orice operatie de tip pop_front() trebuie sa se faca fix o operatie de tip write(x)

Exemplu

Cum se trimit solutii?