Zawody stałe, runda 24
Limit czasowy: 1s; Limit pamięciowy: 32MB
Bibliotekarz
W Wielkiej Wrocławskiej Bibliotece Publicznej pracuje pan Władek. Właśnie przechodził obok półki, na najwyższej półce której leży 42 tomowa Encyklopedia Życia, Wszechświata i Wszystkiego Innego. Władek spojrzał na półkę i zadumał się. "Ech, gdyby ludzie odkładali tomy na swoje miejsce..." - pomyślał. Sprawa jest na tyle skomplikowana, że aby przestawić tomy na swoje miejsce pan Władek musi:
- wejść na Bardzo Wielką Drabinę
- wziąć do ręki tom Encyklopedii Życia, Wszechświata i Wszystkiego Innego
- ze względów bezpieczeństwa zejść z drabiny
- przestawić drabinę w miejsce docelowe
- wejść na drabinę
- odstawić tom na właściwe miejsce
- zejść z drabiny
Bardzo zmartwiony pan Władek załamał ręce. "To zajmie mi cały dzień!" - westchnął. Chwilę, chwilę! Przecież Ty możesz mu pomóc! Oblicz ile tomów trzeba przestawić, aby posortować dużą encyklopedię. Podstawową operacją jest (nie, nie - wcale nie wchodzenie na drabinę) wyciągnięcie pewnej książki i wepchnięcie jej w inne miejsce:
Mając daną kolejność w jakiej są ułożone tomy pewnej książki oblicz ile co najmniej potrzebnych jest takich operacji, aby posortować tomy w rosnącej kolejności.
Wejście:
W pierwszej linijce standardowego wejścia znajduje się jedna liczba N () oznaczająca liczbę tomów do posortowania. W następnej linijce znajduje się permutacja liczb od 1 do N, oznaczająca aktualną kolejność tomów na półce.
Wyjście:
W jedynej linijce standardowego wyjścia należy wypisać jedną liczbę oznaczającą minimalną liczbę operacji jakie należy wykonać aby posortować tomy na półce.
Przykład:
Dla danego wejścia:
6
5 1 2 4 3 6
Poprawną odpowiedzią jest:
2
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany.
Zaloguj się lub
załóż konto.