Żołnierze
Limit pamięci: 32 MB
Na porannym apelu w koszarach wszyscy przebywający tam żołnierze muszą
ustawić się w szeregu. Nie mogą jednak stanąć w dowolnej
kolejności, tylko od najwyższego do najniższego.
Najwyższy może przy tym stać zarówno z lewej, jak i z prawej strony.
Pomóż im wyznaczyć liczbę sposobów, na jakie mogą ustawić się poprawnie.
Dwa ustawienia żołnierzy uważamy za identyczne wtedy i tylko wtedy, gdy
każdy żołnierz w obu ustawieniach ma tego samego sąsiada po lewej
stronie (lub w obu nie ma go wcale) oraz w obu ustawieniach ma
tego samego sąsiada po prawej stronie (lub w obu nie ma go wcale).
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia opis wszystkich przebywających
w koszarach żołnierzy,
-
wyznaczy liczbę ustawień żołnierzy w jednym rzędzie w kolejności
od najwyższego do najniższego,
-
wypisze cztery ostatnie cyfry dziesiętne wyniku na standardowe
wyjście.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita
(), oznaczająca liczbę żołnierzy w koszarach.
Drugi wiersz wejścia zawiera liczb całkowitych
(), pooddzielanych pojedynczymi odstępami
i oznaczających wysokości kolejnych żołnierzy.
Wyjście
Twój program powinien wypisać w pierwszym i jedynym wierszu wyjścia cztery
ostatnie cyfry dziesiętne liczby ustawień żołnierzy w jednym rzędzie
w kolejności posortowanej względem ich wysokości.
Jeżeli wynik jest mniejszy niż , to należy wypisać
wszystkie jego cyfry.
Przykład
Dla danych wejściowych:
7
2 3 1 4 4 5 2
poprawną odpowiedzią jest:
8
Uwaga: Możesz założyć, że w 50% testów jest spełniony warunek
.
Komentarz do przykładu
Oto wszystkie poprawne ustawienia żołnierzy z przykładu
(w nawiasach znajdują się wysokości żołnierzy, a poza nimi - ich numery,
zgodne z kolejnością z wejścia):
3 (1), 1 (2), 7 (2), 2 (3), 4 (4), 5 (4), 6 (5)
3 (1), 7 (2), 1 (2), 2 (3), 4 (4), 5 (4), 6 (5)
3 (1), 1 (2), 7 (2), 2 (3), 5 (4), 4 (4), 6 (5)
3 (1), 7 (2), 1 (2), 2 (3), 5 (4), 4 (4), 6 (5)
6 (5), 4 (4), 5 (4), 2 (3), 1 (2), 7 (2), 3 (1)
6 (5), 5 (4), 4 (4), 2 (3), 1 (2), 7 (2), 3 (1)
6 (5), 4 (4), 5 (4), 2 (3), 7 (2), 1 (2), 3 (1)
6 (5), 5 (4), 4 (4), 2 (3), 7 (2), 1 (2), 3 (1)
Autor zadania: Marian M. Kędzierski.