Mikrokonkurs programistyczno algorytmiczny

[Crow 0]

Witam wszystkich i zapraszam serdecznie do udziału w mikro konkursie programistyczno-algorytmicznym. Zwycięzca otrzyma od PCCentre grę komputerową przy której będzie mógł się "odmóżdżać" w trakcie długich jesienno-zimowych wieczorów.

 

Konkurs będzie polegał na rozwiązaniu 3 wmiare 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#

 

Programy należy pisać "dla konsoli"... tzn. żadnych okienek itp. Program ma wczytać dane ze standardowego wejścia, a następnie wypisać na nie odpowiedź (Jest to standardowa forma konkursowa). Niewolno również używać żadnych dodatkowych bibliotek programowania poza tymi, które umożliwiają wczytanie danych z wejścia (np. iostream lub cstdio w C++; w Pascalu wystarczy read,readln,write,writeln). Rozwiązanie powinno składać się TYLKO z jednego pliku zawierającego kod źródłowy.

 

Odpowiedzi będą sprawdzane zarówno automatycznie jak i ręcznie, prosimy więc o opatrywanie kodu stosownymi i dość treściwymi komentarzami. Oprócz kodu źródłowego e-mail powinien również zawierać krótki, słowny opis zastosowanego algorytmu (czasami wystarczy jego nazwa).

 

Punkty będą przyznawane następująco:

 

Za każde zadanie można dostać 10 punktów za czas jego wykonania. Maksymalną ilość punktów otrzymuje się za przysłanie rozwiązania na 10 dni przed jego terminem końcowym. Licząc, że na każde zadanie będziecie mieli 14 dni, to wysyłając rozwiązanie w ciągu tych pierwszych 4 dni dostaniecie 10 pkt. Począwszy od dnia 10-tego ilość punktów będzie się zmniejszać o 1 każdego dnia.

 

Dodatkowo każdy program zostanie oceniony w skali 0-5 przez sprawdzającego. Ocena ta będzie uwzględniać jasność kodu, jego efektywność itp. (Niestety będzie zatem subiektywna... do czasu powstania automatycznej testerki takie jest to jedyne możliwe rozwiązanie)

 

W treści każdego zadania będzie podana jego wymagana złożoność czasowa. Algorytmy o innej złożoności będą niestety odrzucane.

 

W przypadku remisu lub braku możliwości wyłonienia zwycięzcy zostanie przeprowadzona dogrywka.

 

Zadanie 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 nieusuwając jej 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 jeszcze raz 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ślajaca 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". W przypadku 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