Revizia anterioară Revizia următoare
| 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 valoare 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 din output ii contine, urmat de caracterel ": ". 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 ≤ 100 000
- O operatie de push se considera valida daca valoare folosita se afla in WR.
- Toate valorile folosite in operatiile de push vor fi distincte.
Exemplu
| queue.in | queue.out |
|---|---|
| 5 2 push_back(3) push_back(5) push_front(1) pop_front() pop_back() | 1: read(3) push(1,3) 2: read(5) push(1,5) 3: pop(1) push(2,5) pop(1) push(2,3) read(1) push(2,1) 4: pop(2) write(2) 5: pop(2) push(1,3) pop(2) write(5) |
Explicaţie
...
