Trwałe struktury danych

07.06.2010 - Filip Sieczkowski
TrudnośćTrudnośćTrudnośćTrudność

Zadania


Trwały stos

W tym zadaniu należy zaimplementować stos, który poza standardowymi operacjami (push, pop i top) będzie umożliwiał wykonywanie operacji undo oraz redo.  Program musi działać online, czyli musi odpowiedzieć na każde zapytanie zanim otrzyma kolejne (należy pamiętać o wymuszeniu wypisania odpowiedzi funkcją fflush(w stdio) lub flush(w iostream)).

Dane wejściowe

W pierwszym wierszu znajduje się jedna liczba naturalna n, 1 <= n <= 106. W kolejnych n wierszach znajdują się zapytania następującej postaci:

  • "PUSH n", gdzie 1 <= n <= 109, oznaczające dodanie do stosu liczby n.

  • "POP", oznaczające usunięcie elementu ze szczytu stosu (to zapytanie występuje tylko przy niepustym stosie).
  • "TOP", oznaczające pytanie o element znajdujący się na szczycie stosu.
  • "UNDO n", gdzie 1 <= n <= 106, oznaczające cofnięcie ostatnich n operacji typu PUSH lub POP. Liczba n nigdy nie będzie większa niż aktualna ilość operacji od początkowego stanu stosu.
  • "REDO n", gdzie 1 <= n <= 106, oznaczająca odtworzenie n spośród wcześniej cofniętych operacji typu PUSH lub POP. Odtworzenie operacji może nastąpić tylko jeśli stos nie został zmodyfikowany (operacjami PUSH lub POP) od czasu ostatniej instrukcji UNDO. Jeśli instrukcja REDO pojawi się w treści, zawsze będzie możliwa do wykonania.

Przyjmujemy, że na początku programu stos jest pusty (dla pustego stosu nigdy nie pojawią się zapytania TOP ani POP).

Specyfikacja wyjścia

Dla każdego zapytania  należy wypisać odpowiedź w osobnej linii. Dla zapytania TOP odpowiedzią jest liczba znajdująca się aktualnie na szczycie stosu, dla pozostałych zapytań -- napis "OK". Dopiero po wypisaniu odpowiedzi na aktualne zapytanie możliwe będzie wczytanie kolejnego.

Przykład

Dla danych wejściowych:

10
PUSH 4
PUSH 5
TOP
PUSH 6
UNDO 2
TOP
UNDO 1
REDO 2
POP
TOP

poprawną odpowiedzią jest:

OK
OK
5
OK
OK
4
OK
OK
OK
4


Zbiory i czas

Wszyscy umiemy efektywnie reprezentować zbiory, potrafimy też szybko znajdować w zbiorze ograniczenia górne i dolne elementów. Ale tym razem możemy dodatkowo "podróżować w czasie": nowy zbiór możemy stworzyć dodając elementy nie tylko do aktualnego zbioru, ale również do dowolnego wcześniej stworzonego zbioru. Podobnie szukać ograniczeń możemy również we wcześniejszych wersjach zbiorów. Czy potrafisz robić to efektywnie?

Zadanie jest sprawdzane online -- program musi odpowiedzieć na aktualne zapytanie zanim pozna kolejne!

(Uwaga: W ramach ułatwienia, zbiory można tylko rozszerzać; jeśli jednak czujesz się na siłach, spróbuj zaimplementować również usuwanie, które jest bardziej skomplikowane niż zazwyczaj)

Dane wejściowe:

W pierwszym wierszu znajduje się jedna liczba naturalna n, 1 <= n <= 200000. W kolejnych n wierszach znajdują się zapytania następującej postaci:

  • "INSERT k m", gdzie  0 <= k <= n, -109 < m < 109. Zapytanie oznacza storzenie nowego zbioru poprzez dodanie do zbioru o numerze k liczby m. Liczba k nigdy nie będzie większa niż liczba stworzonych wcześniej zbiorów.
  • "BOUNDS k m", gdzie 0 <= k <= n, -109 < m < 109; jest to pytanie o największą liczbę nie większą niż m (ograniczenie z dołu), oraz najmniejszą liczbę nie mniejszą niż m (ograniczenie z góry), znajdujące się w k-tym zbiorze. Podobnie jak w przypadku INSERT, k zawsze oznacza dobrze zdefiniowany zbiór.

Za początkowy zbiór, oznaczany numerem 0, przyjmujemy zbiór pusty.

Specyfikacja wyjścia:

Dla każdego zapytania należy wypisać odpowiedź w osobnej linii. W przypadku zapytania INSERT odpowiedzią jest napis "OK". Dla zapytania BOUNDS, odpowiedzią są dwie liczby oddzielone spacją, oznaczające odpowiednio ograniczenie dolne i ograniczenie górne. Jeśli któreś z tych ograniczeń nie istnieje, zamiast niego program powinien wypisać "-INF" dla ograniczenia dolnego, lub "INF" dla górnego. Ewentualne wątpliwości powinien rozwiać przykład. Dopiero po wypisaniu odpowiedzi na aktualne zapytanie możliwe będzie wczytanie kolejnego.

Przykład:

Dla następujących danych:

7
BOUNDS 0 6
INSERT 0 5
INSERT 0 7
BOUNDS 2 6
BOUNDS 1 6
INSERT 1 7
BOUNDS 3 6

poprawną odpowiedzią jest:

-INF INF
OK
OK
-INF 7
5 INF
OK
5 7


Naszyjniki

Ala powiedziała: “Mam najpiękniejszy naszyjnik. Składa się -- od lewej do prawej -- z dwóch czerwonych pereł, dwóch zielonych i jeszcze jednej czerwonej”. Basia szybko zripostowała: “Mój jest jeszcze ładniejszy. Jest prawie taki jak Twój, ale musiałabyś usunąć dwie perły z prawej strony i zastąpić je dwiema niebieskimi”. Ledwie zdążyła skończyć, a już odezwała się Cecylia: “Twój się w ogóle nie umywa do mojego: ja mam jeszcze żółtą perłę z lewej”. Nie zdziwi was pewnie, że Dominika też nie została z tyłu: “Wszystkie wasze są nudne. Żeby dostać mój naszyjnik, trzeba by wziąć ten Basi, zabrać po jednej perle z lewej i prawej strony, i dodać dwie czarne po lewej”. I tak dziewczynki przechwalały się, aż w końcu Zosia spytała: “Chwilka, jaka perła była najbardziej z lewej w naszyjniku Ewy?”. Odpowiedziała jej cisza. Pomóż dziewczynkom!

Zadanie jest sprawdzane online -- program musi odpowiedzieć na aktualne zapytanie, zanim otrzyma kolejne: w końcu dziewczynki nie będą czekać na swoje odpowiedzi aż wszystkie zadadzą pytania. ;)

Uwaga: przy wypisywaniu odpowiedzi pamiętaj o wymuszeniu wysłania jej (funkcją fflush w bibliotece stdio lub flush/endl w iostream).

Dane wejściowe.

W pierwszym wierszu znajduje się jedna liczba naturalna n, 1 <= n <= 100000. W kolejnych n wierszach znajdują się zapytania następującej postaci:

  • "RL n" -- stwórz nowy naszyjnik przez odcięcie perły z lewego końca naszyjnika n
  • "RR n" -- analogicznie do RL, ale z prawego końca
  • "AL n k" -- stwórz nowy naszyjnik przez dodanie do naszyjnika n z lewej strony perły koloru k (0 <= k <= 109)
  • "AR n k" -- analogicznie do AL, ale z prawej strony
  • "QL n" -- wypisz kolor perły z lewego końca naszyjnika n
  • "QR n" -- analogicznie do QL, ale z prawego końca

Początkowy naszyjnik jest pusty, i ma numer 0. Zapytania RL, RR, AL i AR tworzą nowy naszyjnik o numerze o jeden większym niż aktualnie największy. Zapytania RL, RR, QL i QR nigdy nie będą dotyczyły pustego naszyjnika, we wszystkich zapytaniach n będzie się odnosiło do już stworzonego naszyjnika.

Specyfikacja wyjścia.

Dla każdego zapytania należy wypisać odpowiedź w osobnej linii. Dla zapytań QL i QR odpowiedzią jest wartość odpowiedniej perły (tak jak opisana w danych wejściowych), dla pozostałych zapytań -- napis "OK". Dopiero po wypisaniu odpowiedzi na aktualne zapytanie możliwe będzie wczytanie kolejnego.

Przykład.

Dla następujących danych wejściowych:

7
AL 0 5
QR 1
QL 1
AR 1 10
RL 2
QL 2
QL 3

poprawnym wynikiem jest:

OK
5
5
OK
OK
5
10

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com