== include(page="template/taskheader" task_id="mstack") ==
Poveste şi cerinţă...
Bulănel tocmai a descoperit o problemă interesantă de structuri de date şi s-a gîndit să o propună la concursul la care voi tocmai participaţi. Voi trebuie să implementaţi o structură de date pe care o vom numi MStack, care suportă toate operaţiile pe care le suportă o stivă obişnuită $(push, pop, top)$ plus operaţia $middle$ (care returnează elementul aflat la jumătatea stivei). Deoarece această problemă ar fi fost prea uşoară, Bulănel adaugă urmatoarele restricţii: MStack-ul vostru poate folosi ca structură internă de stocare doar $13$ stive obişnuite (numerotate de la $1$ la $13$), iar numărul de operaţii asupra acestora trebuie să fie mai mic sau egal decît 5 * numărul operaţiilor asupra MStack-ului.
Operaţiile care vor fi executate asupra MStack-ului sunt:
* $push$: adaugă valoarea $x$ in vârful MStack-ului, unde $x$ este egal cu numărul de operaţii $push$ efectuate pâna în momentul curent;
* $top$: returnează valoarea din vârful MStack-ului;
* $middle$: returnează valoarea care se află la jumătatea MStack-ului (daca sunt $N$ elemente în stiva, elementul din mijlocul stivei se gaseşte pe poziţia $N/2+1$ numărând de la baza stivei);
* $pop$: elimină elementul din vârful MStack-ului.
Pentru ca voi să nu trişati, va trebui ca operaţiile pe care le efectuaţi asupra celor $13$ stive să le scrieţi în fişierul de ieşire, iar operaţiile permise sunt:
* $move a b$: mută elementul din vârful stivei $a$ în vârful stivei $b$;
* $pop a$: aruncă elementul din vârful stivei $a$;
* $push a$: adaugă în vârful stivei a valoarea $x$, unde $x$ este egal cu numărul de operaţii push efectuate pâna in momentul curent;
* $top a$: răspunde la operaţia top sau middle a MStack-ului, adică în vârful stivei a se află elementul din vârful MStack-ului sau din mijlocul MStack-ului.
h2. Cerinţa
Dându-se un set de operaţii care vor fi executate asupra MStack-ului, voi trebuie să execuţati o succesiune de operaţii asupra celor $13$ stive astfel încât:
* Pentru fiecare operaţie $push$ sau $pop$ din fişierul de intrare există o singură operatie $push$ sau $pop$ în fişierul de ieşire, păstrând ordinea din fişierul de intrare;
* Pentru fiecare operatie $top$ si $middle$ din fişierul de intrare există o singură operaţie $top$ în fişierul de ieşire, păstrând ordinea din fişierul de intrare;
* La toate operaţiile $push$, $top$ şi $middle$ trebuie să se răspundă exact în ordinea din fişierul de intrare
* Operaţia $move$ poate fi inserată între oricare două operaţii.
h2. Date de intrare
Fişierul de intrare $mstack.in$ ...
Fisierul de intrare $mstack.in$ conţine pe prima linie numărul de operaţii $N$, iar pe urmatoarele $N$ linii vor fi descrise cele $N$ operaţii, câte una pe linie.
h2. Date de ieşire
În fişierul de ieşire $mstack.out$ ...
Fisierul de iesire $mstack.out$ conţine operaţiile care vor fi executate asupra celor $13$ stive, câte o operaţie pe linie, în ordinea în care vor fi executate.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1 000 000$
* Pentru $30%$ din teste $1 ≤ N ≤ 1000$
* Se garantează că nu se va efectua nici o operaţie $pop$ când MStack-ul este gol.
* **Atenţie!** Pentru a primi punctajul pe un test, numărul de operaţii din fişierul de ieşire trebuie sa fie mai mic sau egal cu 5 * numarul de operaţii din fişierul de intrare.
h2. Exemplu
table(example). |_. mstack.in |_. mstack.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6
push
push
push
middle
pop
top
| push 1
push 2
push 3
top 2
pop 3
top 2
|
h3. Explicaţie
...
Se inserează în MStack elementele $1$, $2$ si $3$. $Middle$ are ca rezultat valoarea $2$, apoi se elimina $3$, iar $top$-ul din urmă are ca rezultat tot valoarea $2$.
Intern, se insereaza in stiva $1$ elementul $1$, in stiva $2$ elementul $2$ si in stiva $3$ elementul $3$. Pentru a obtine $middle$-ul apelam $top$-ul stivei $2$. Pentru $pop$ apelam $pop$-ul stivei $3$, iar pentru ultimul $top$ apelam $top$-ul stivei $2$.
== include(page="template/taskfooter" task_id="mstack") ==
