Hossa

28.10.2010
TrudnośćTrudność

Hossa

Limit czasowy: 1000 milisekund
Limit pamięciowy: 32000 kilobajtów


Na giełdy światowe na dobre powróciły wzrosty i od dawna mówi się o kolejnej hossie. Czym dokładnie jest jednak hossa? Na to pytanie postanowił odpowiedzieć znany matematyk i ekonomista - pan Wacław. Pan Wacław przez wiele miesięcy starał się określić ścisłe granice hoss i bess na wykresie Warszawskiego Indeksu Giełdowego (WIG). Wreszcie, po wielu nieudanych próbach, Pan Wacław podał formalną definicję, która jego zdaniem w pełni opisuje moment wystąpienia hossy na giełdzie. Oto ona:

Niech a1, a2, ...., an  - wartość WIG w kolejnych dniach notowań. Możemy założyć, że jest to n-elementowy ciąg różnych liczb naturalnych. Mówimy, że ciąg a jest hossą wtedy, gdy dla każdych trzech pozycji w ciągu i, j, k (i<j<k) jeżeli ai<aj to ak>ai. Intuicyjnie, jeżeli między dwoma dniami i oraz j kurs wzrósł z ai do aj to mamy pewność, że kurs nigdy nie spadnie w kolejnych dniach do lub poniżej wartości ai.

Przykładowo, wszystkie hossy składające się z 4 elementów 1,2,3,4 to:
(1,2,3,4), (2,1,3,4), (1,3,2,4), (3,1,2,4), (3,2,1,4), (1,2,4,3), (2,1,4,3), (1,4,2,3), (1,4,3,2), (4,1,2,3), (4,2,1,3), (4,1,3,2), (4,3,1,2), (4,3,2,1)
Hossą nie jest na przykład ciąg (3,2,4,1), bo kurs wzrósł z 3 do 4, a później spadł do 1.

Każdą hossę możemy zapisać jako LmR - gdzie: m - najwyższa wartość w ciągu, L - elementy ciągu po lewej stronie m, P - elementy ciągu po prawej stronie m. Przykładowo, dla hossy (1,2,4,3): m = 4, L = (1,2), P = (3). Łatwo zauważyć, że elementy L (lub P) tworzą hossę składającą się z mniejszej liczby elementów.

Definicja hossy Pana Wacława odniosła ogromny sukces - został on nawet zaproszony na Wall Street, aby publicznie wygłosić referat. Jednym z jego elementów jest przedstawienie kilku przykładów ciągów, które są hossami. Aby o żadnej nie zapomnieć, Pan Wacław postanowił wprowadzić porządek, który pozwoliłby na porównanie ze sobą dwóch hoss. Oto jego definicja:

Mówimy, że dla dwóch różnych hoss H1 = L1mP1 i H2 = L2mP2 zachodzi H1<H2 (hossa H1 jest mniejsza od hossy H2) wtedy gdy, H1 i H2 składają się z tych samych liczb (H2 jest permutacją elementów ciągów H1) oraz:
a) liczba elementów w P1 jest mniejsza od liczby elementów w P2
b) jeżeli liczba elementów P1 i P2 jest taka sama to sprawdzamy czy P1 < P2 (czyli czy hossa P1 jest mniejsza od hossy P2)
c) jeżeli P1 jest tym samym ciągiem co P2, to sprawdzamy czy L1 < L2

Przykładowo, możemy posortować wszystkie hossy składające się z 4 elementów i otrzymać ciąg hoss przedstawiony w pierwszej definicji. Niektóre z możliwych porównań:
(1,2,3,4) < (2,1,3,4) - zachodzi przypadek c, tj. (1,2,3) < (2,1,3). Możemy stwierdzić, że (1,2,3) < (2,1,3), ponieważ znowu zachodzi przypadek c, tj. (1,2)<(2,1). Możemy stwierdzić, że (1,2)<(2,1), ponieważ zachodzi przypadek a.
(1,4,2,3) < (1,4,3,2) - zachodzi przypadek b, tj. (2,3) < (3,2).

Tuż przed wyjazdem, Pan Wacław zalał kawą jeden z przykładów przygotowanych do pokazania maklerom na Wall Street. Szczęśliwie wie on, że zalana hossa jest bezpośrednim następnikiem pewnej innej hossy H. Pan Wacław poprosił Ciebie, żebyś napisał program, który pomoże mu odtworzyć ten przykład. Innymi słowy, Twoim zadaniem jest mając dany opis hossy H, wypisać elementy hossy X, takiej że:
- H < X
- dla każdej innej od X hossy H', takiej że H<H', zachodzi X<H'
Możesz założyć, że dla danych testowych taka hossa zawsze istnieje.

Przykładowo, bezpośrednim następnikiem hossy (1,2,3,4) jest (2,1,3,4), (2,1,3,4) jest (1,3,2,4), (1,3,2,4) jest (3,1,2,4), itd.

Wejście:

W pierwszej linii wejścia znajduje się jedna liczba całkowita n (2<=n<=1000000). W następnej linii znajduje się n różnych liczb naturalnych, nie większych od 1000000, oddzielonych pojedynczym odstępem. Są to kolejne elementy pewnej hossy H.

Wyjście:

Twój program powinien wypisać ciąg n liczb naturalnych oddzielonych pojedynczym odstępem. Są to kolejne elementy hossy będącej bezpośrednim następnikiem hossy H.

Przykład:

Dla danych wejściowych:
4
20 10 30 40

poprawną odpowiedzią jest:
10 30 20 40

Dla danych wejściowych:
10
3 2 1 10 9 8 7 6 5 4

poprawną odpowiedzią jest:
1 2 10 3 4 5 6 7 8 9

Dla danych wejściowych:
10
3 2 1 10 4 5 7 6 9 8

poprawną odpowiedzią jest:
1 2 3 10 5 4 7 6 9 8

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com