Zadanie 2. Pomniki w Megabajtach Wielkich

Z okazji stulecia niepodległości Megabajtów Wielkich postanowiono uwiecznić w postaci pomników najważniejsze postacie w historii kraju – polityków, działaczy, naukowców, sportowców oraz artystów. Ze względu na zasługi pomniki różniły się wielkością i miały zostać ustawione od najniższego do najwyższego na głównej ulicy stolicy.

Niestety, firma odpowiedzialna za rozmieszczenie monumentów ustawiła je w losowej kolejności, zostawiając na miejscu zaledwie dwa dźwigi, którymi można podnieść pojedynczy pomnik. Dźwigi mają ograniczony zasięg i mogą przestawić pomnik jedynie na jego sąsiednie miejsca w szeregu (oczywiście jeżeli były one puste lub drugi dźwig podniósł wcześniej znajdujący się tam inny pomnik).

Co więcej, dźwigi zawsze przesuwają się od początku ulicy do jej końca i zawsze zamieniają pomnik wyższy z niższym, jeżeli wyższy stoi wcześniej (patrząc od początku ulicy). Dźwigi wracając z końca ulicy, po zakończeniu cyklu pracy nie dokonują żadnych zamian. Następnie przed rozpoczęciem kolejnego cyklu pracy dźwigi są tankowane. Dopiero po zatankowaniu wracają one na miejsce startu cyklu pracy.

Ze względu na charakter uroczystości zdecydowano się uporządkować pomniki. Prezydent stolicy poprosił o podanie oczekiwanego czasu operacji.

Analiza poglądowa wykazała, że zamiana dwóch sąsiadujących ze sobą pomników miejscami i dotarcie dźwigów do końca ulicy trwa godzinę, na dojazd dźwigów z końca ulicy na stację paliw potrzeba 45 minut, tankowanie dźwigów trwa 15 minut, a czas potrzebny na ich powrót ze stacji paliw do punktu startu pracy wynosi 30 minut.

W pliku pomniki.txt znajdują się wysokości $50$ pomników wyrażone w metrach, w kolejności odpowiadającej tej na ulicy, każda wysokość w osobnej linii. Wysokości to liczby naturalne z przedziału $<10,50>$.

Napisz program, który dla danych z pliku pomniki.txt wyznaczy zaokrągloną w górę liczbę godzin potrzebnych do uporządkowania monumentów. Załóż, że po dokonaniu ostatniej zamiany dźwigi są tankowane i wracają do punktu startu. Wynik zapisz w pliku operacje.txt. W obliczeniach uwzględnij całkowity czas trwania wszystkich etapów cyklu zamiany.

Do oceny oddajesz:

• plik operacje.txt zawierający odpowiedź (liczbę naturalną będącą zaokrągloną w górę liczbą godzin potrzebnych do uporządkowania monumentów),

• plik(i) z komputerową realizacją zadania (kodem programu).

Rozwiązanie

Odpowiedź dla danych z pliku pomniki.txt