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 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 se considera valida daca valoare folosita se afla in WR.
- Toate valorile folosite in operatiile de push vor fi distincte.
- Punctajul de 100p se va acorda doar daca in fisierul de output vor fi mai putin de 100 000 instructiuni pentru cele N operatii.
- Pe fiecare linie a fisierului de output puteti afisa maximum 500 000 caractere, altfel outputul se va considera invalid.
Exemplu
| queue.in | queue.out |
|---|---|
| 5 push_back(3) push_back(5) pop_front() pop_front() push_back(2) | 1: read(3) push(1,3) 2: read(5) push(1,5) 3: pop(1) push(2,5) pop(1) write(3) 4: pop(2) write(5) 5: read(2) push(2,2) |
