Fişierul intrare/ieşire:mstack.in, mstack.outSursăLot Deva 2013 - Baraj 2 Seniori
AutorCosmin-Mihai TutunaruAdăugată deGavrilaVladGavrila Vlad GavrilaVlad
Timp execuţie pe test1.4 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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

mstack.inmstack.out
6
push
push
push
middle
pop
top
push 1
push 2
push 3
top 2
pop 3
top 2

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content