Runda 24 - Bibliotekarz

22.03.2010 - Krzysztof Piecuch
Trudność

 

 

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 ($ 1 \leq N \leq 100 000 $) 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.
PozycjaImię i nazwiskoWynikCzas
1Przemysław Derengowski1005:26:37
2Anna Piekarska1013:40:11
3Krzysztof Drab1037:08:51
4Kamil Łukasz1099:11:19
5Darek Bukowski10129:58:28
6Krzysztof Kulig10156:27:19
7Krzysztof Jamróz10920:28:11
8Michał Krawczak106782:30:53
9Witold Długosz109018:04:51
10Dominik Nabiałek63678:55:57
11Michał Zezyk58006:55:01
4.5
Twoja ocena: Brak Ocena: 4.5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com