| Historia OI -> III OI 1995/1996 -> Zadania |  |
|
III Olimpiada Informatyczna 1995/96
|
|
Zadanie: KUL
|
Autor: Krzysztof Diks
|
| Zawody III stopnia |
| Plik źródłowy: | KUL.??? (np. pas, c, cpp) |
| Plik wykonywalny: | KUL.exe |
| Plik wejściowy: | KUL.in |
| Plik wyjściowy: | KUL.out |
Na okręgu umieszczono n pudełek ponumerowanych zgodnie z ruchem wskazówek zegara od 1 do n, gdzie 1 <= n <= 1000. W pudełkach znajdują się kule, przy czym łącznie we wszystkich pudełkach jest ich nie więcej niż n.
Należy przełożyć kule w taki sposób, żeby w każdym pudełku pozostała co najwyżej jedna kula. W jednym ruchu można przełożyć jedną kulę z pudełka, w którym się znajduje, do pudełka sąsiedniego.
Zadanie
Ułóż program, który:- wczytuje z pliku tekstowego KUL.IN liczbę pudełek n i rozmieszczenie kul w pudełkach,
- oblicza minimalną liczbę ruchów, jakie trzeba wykonać, aby w każdym pudełku była co najwyżej jedna kula,
- zapisuje tę liczbę w pliku tekstowym KUL.OUT.
Wejście
W pierwszym wierszu pliku tekstowego KUL.IN jest zapisana jedna liczba całkowita dodatnia. Jest to liczba pudełek n. W każdym z kolejnych n wierszy jest zapisana jedna liczba całkowita nieujemna. W i-tym z tych wierszy jest zapisana liczba kul w i-tym pudełku.
Wyjście
W pliku tekstowym KUL.OUT należy zapisać jedną liczbę całkowitą nieujemną tj. minimalną liczbę ruchów, jakie trzeba wykonać, aby w każdym pudełku była co najwyżej jedna kula.
Przykład
Dla pliku KUL.IN:12
0
0
2
4
3
1
0
0
0
0
0
1
w pliku KUL.OUT należy zapisać:
19
Twój program powinien szukać pliku KUL.IN w katalogu bieżącym i tworzyć plik KUL.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę KUL.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku KUL.EXE.