Fişierul intrare/ieşire:queue.in, queue.outSursăAlgoritmiada 2013, Runda 2
AutorSerban Andrei StanAdăugată deGheorgheMihaiMihai Gheorghe GheorgheMihai
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 ≤ 106.
  • 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

queue.inqueue.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)
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?