Fişierul intrare/ieşire:	mstack.in, mstack.out	Sursă	Lot Deva 2013 - Baraj 2 Seniori
Autor	Cosmin-Mihai Tutunaru	Adăugată de	Gavrila Vlad •GavrilaVlad
Timp execuţie pe test	0.7 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Mstack

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.

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.

Date de intrare

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.

Date de ieşire

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.

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.

Exemplu

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.

Cum se trimit solutii?