Konkurs programistyczno-algorytmiczny na PC Centre!

Zapraszamy serdecznie wszystkich do udziału w konkursie programistyczno-algorytmicznym organizowanym przez nasz serwis. Zwycięzca otrzyma od PC Centre grę komputerową, przy której będzie mógł się relaksować w trakcie długich jesienno-zimowych wieczorów. Konkurs polega na rozwiązaniu trzech prostych zadań programistyczno-algorytmicznych. Swoje odpowiedzi (w postaci kodu źródłowego) będziecie musieli przesłać przed końcem wyznaczonego czasu na adres e-mail podany w zadaniu. Dopuszcza się stosowanie następujących języków programowania: C/C++ (GCC, Dev-Cpp, Visual Studio) Pascal (Turbo Pascal, FreePascal) Java C# Więcej informacji znajdziecie w temacie założonym na naszym forum.

Zadanie pierwsze (A): Super-Stos

Twoim pierwszym zadaniem będzie zaimplementowanie stosu, który oprócz standardowych operacji PUSH i POP ma udostępniać również specjalną operację MIN. Wypisuje ona wartość najmniejszego elementu znajdującego się w stosie nie usuwając go z niego. Co najważniejsze WSZYSTKIE OPERACJE MUSZĄ DZIAŁAĆ W CZASIE O(1) (czyli stałym względem ilości elementów na stosie - wszelkie inne rozwiązania będą odrzucane).

Rozwiązania w postaci JEDNEGO pliku z kodem źródłowym należy przysyłać na adres e-mail: kamil.bartocha@pccentre.pl do dnia 02.12.06.

Przypominam raz jeszcze o opatrywaniu kodu stosownymi komentarzami oraz o krótkim opisie zastosowanego algorytmu w treści e-maila (wystarczy ogólna idea).

Wejście

W pierwszej lini standardowego wejścia znajduje się liczba z określająca ilość zestawów danych (1 <= z <= 2147483600). Opis pojedynczego zestawu jest następujący:

Pierwsza linia zawiera liczbę całkowitą n (1 <= n <= 1000000) będącą liczbą operacji do wykonania. Kolejne n linii zawiera listę operacji które należy wykonać, gdzie każda linia ma jedną z postaci:

• "0 k" - co oznacza PUSH k (gdzie 0 <= k <= 2147483600)
• "1" - co oznacza POP
• "2" - co oznacza MIN

Wyjście

Dla każdego zestawu danych wypisz kolejno wyniki operacji POP (wartość ściąganą ze szczytu stosu) i MIN (wartość najmniejszą występującą w stosie). W przypadku, gdy zadaną operacją jest "POP", a stos jest pusty, należy wypisać na wyjście "EMPTY". Gdy operacją jest "MIN", a stos jest pusty, należy wypisać "NOMIN".

Przykład

Wejście:
3
5
0 5
0 2
0 7
2
1
7
0 7
2
1
1
2
0 1
0 2
7
0 2
0 1
2
1
2
1
2

Wyjście:
2
7
7
7
EMPTY
NOMIN
1
1
2
2
NOMIN