Runda 33 - Ciężkie klocki

14.06.2010 - Damian Rusak
TrudnośćTrudność

 

Zawody stałe, runda 33,

Limit czasowy: 2s; Limit pamieciowy: 32MB


Ciężkie klocki

 

Mały Bobbie otrzymał na urodziny zestaw klocków. Jego rodzice wiedzieli dobrze, że nie jest to zbyt oryginalny prezent i gdzieś już słyszeli o dzieciach otrzymujących różne odmiany stymulujących intelektualnie klocków. Postanowili więc tym razem postawić nie na rozmiar, lecz na wagę. Każdy z fascynujących klocków ma swoją wagę, wyrażającą się liczbą całkowitą dodatnią. Żadne dwa klocki nie ważą tyle samo. Na nieszczęście dla Bobbiego jego rodzice są miłośnikami zagadek logicznych, postanowili więc przerwać jego beztrosko prymitywną zabawę i przygotować dla niego zadanie do wykonania.

Klocki zostały ustawione w rzędzie, jeden obok drugiego. Rodzice wyjaśnili Bobbiemu że klocki są tak skonstruowane, że jeśli któryś z nich zostanie popchnięty w jedną ze stron, to przewróci wszystkie lżejsze od niego (na zasadzie domina) po tej stronie, aż do pierwszego klocka cięższego niż ten popchnięty, bądź do pierwszego miejsca, gdzie jest przewrócony wcześniej klocek. Z uśmiechami na ustach zaproponowali Bobbiemu, że jeśli uda mu się znaleźć sposób na przewrócenie wszystkich klocków w najmniejszej możliwej liczbie "popchnięć", to będzie mógł powrócić do swych poprzednich infantylnych zabaw.

Oczywiście Bobbie ani myśli się tym zajmować, woli oglądać wzorki na dywanie. Ale Ty możesz podjąć wspaniały zamiar i pomóc Bobbiemu poprzez napisanie programu, który odnajdzie żądaną liczbę popchnięć klocków.

Wejście:

Pierwsza linia wejścia zawiera liczbę całkowitą $ n $ - liczbę klocków. ($ 1\leq n \leq 1000 $). W kolejnej linii znajduje się $ n $ różnych liczb całkowitych z przedziału od $ 1 $ do $ 10^{9} $ - wagi kolejnych klocków ustawionych w rzędzie.

Wyjście:

Jedyna linia wyjścia powinna zawierać jedną liczbę - najmniejszą liczbę popchnięć klocków potrzebną do przewrócenia ich wszystkich.

Przykład:

Wejście:

7
3 5 7 2 1 6 4

Wyjście:

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
1Krzysztof Drab1011:15:02
2Adam Tażyk1013:55:58
3Arek Wróbel1015:08:20
4Przemysław Derengowski1035:42:45
5Adrian Zgorzałek1062:55:41
6Anna Piekarska1077:28:50
7Grzegorz Głuch10439:51:12
8Michał Kownacki102724:22:07
9Michał Krawczak104758:15:06
10Kamil Dębowski105895:40:41
11Witold Długosz106999:54:44
12Emacs Master82893:55:07
13Robert Kozak85197:01:38
14Bartek Dudek7152:19:12
15Szymon Stankiewicz44335:46:12
16Jakub Stanecki263:20:16
17Dominik Nabiałek276:31:12
18Łukasz Hryniuk16254:49:38
3.75
Twoja ocena: Brak Ocena: 3.8 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com