Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2013-01-13 18:51:07.
Revizia anterioară   Revizia următoare  

 

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.1 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 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.inqueue.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

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?