Runda 3: Kolejarz Paweł

27.10.2009 - Przemysław Pietrzkiewicz
TrudnośćTrudność

Limit czasowy: 10 sekund
Limit pamięciowy: 64 MB

Pan Paweł uwielbiał pociągi jeszcze zanim nauczył się czytać i pisać. Z czasem dziecinne zainteresowanie przerodziło się w pasję, a potem w zawód. Mówiąc krótko - pan Paweł jest kolejarzem na stacji załadunkowej w małej podwrocławskiej miejscowości.


Stacja pana Pawła ma tylko jedną linię kolejową, na której ruch odbywa się w jedną stronę. Pociągi opuszczają stację w kolejności, w której do niej przyjeżdzają. Życie na stacji płynie wolnym tempem, przez większość dnia nic się tam nie dzieje. Spokój zakłóca tylko od czasu do czasu jedno z trzech wydarzeń:

  • przyjazd pociągu o określonej ładowności,
  • wyjazd pociągu znajdującego się na stacji, który pojawił się na niej jako pierwszy,
  • telefon z centrali.

 
Pan Paweł nie znosi telefonów z centrali, biurokraci zawsze pytają o to samo. Chcąc poznać mniej więcej przeciętną ładowność pociągów na stacji proszą pana Pawła o podanie mediany ładowności pociągów na stacji. To doprowadza naszego bohatera do szewskiej pasji - musi za każdym razem zapisać na kartce wszystkie ładowności, posortować je i wyznaczyć środkową (lub dwie środkowe, jeśli jest ich parzyście wiele). Czy potrafisz pomóc panu Pawłowi pisząc odpowiedni program?

Wejście

W pierwszej linii wejścia znajduje się liczba N (1<=N<=106), oznaczająca liczbę wydarzeń na stacji pana Pawła. W kolejnych N liniach znajdują się opisy wydarzeń. Każdy opis jest postaci:

  • "przyjazd X" — oznacza przyjazd na stację pociągu o ładowności X (1<=X<=106),
  • "odjazd" — oznacza odjazd kolejnego pociągu.
  • "telefon" — oznacza telefon z centrali.

 

Centrala gwarantuje, że nie będzie dzwonić, kiedy na stacji nie będzie żadnych pociągów. Zdrowy rozsądek gwarantuje, że w takiej sytuacji żaden pociąg ze stacji nie odjedzie. Zakładamy, że na początku na stacji pana Pawła nie ma żadnych pociągów.

 

Wyjście

Każdemu poleceniu 'telefon' powinna odpowiadać dokładnie jedna (kolejna w porządku zadawania zapytań) linia wyjścia programu. Należy wypisać medianę ładowności pociągów na stacji - jeśli jest ich parzyście wiele, należy wypisać dwie środkowe wartości oddzielone spacją w kolejności niemalejącej.

 

Przykład

Dla danych wejściowych:

 

10
przyjazd 1
telefon
odjazd
przyjazd 3
przyjazd 4
telefon
przyjazd 5
telefon
odjazd
telefon

 

poprawną odpowiedzią jest:

 

1
3 4
4
4 5

 

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