Polish version    English version  
  Historia OI -> VIII OI 2000/2001 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
Zadania
Regulamin
Zasady organizacji
Wskazówki
Terminarz
Statystyki
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
VIII Olimpiada Informatyczna 2000/2001

Zadanie: LAN
Autor: Marcin Kubica
Łańcuch

Zawody III stopnia, dzień drugi 28 marzec 2001
Plik źródłowy: LAN.??? (np. pas, c, cpp)
Plik wykonywalny: LAN.exe
Plik wejściowy: LAN.in
Plik wyjściowy: LAN.out

Bajtocja nie zawsze była państwem demokratycznym. W jej historii były również czarne karty. Pewnego razu, generał Bajtelski -- przywódca junty żelazną ręką rządzącej Bajtocją -- postanowił zakończyć stan wojenny, trwający od momentu przejęcia władzy, i zwolnić więzionych działaczy opozycji. Nie chciał jednak uwolnić przywódcy opozycji Bajtazara. Postanowił przykuć go do murów więzienia za pomocą bajtockiego łańcucha. Bajtocki łańcuch składa się z połączonych ze sobą ogniw oraz przymocowanego do muru pręta. Choć ogniwa nie są połączone z prętem, to bardzo trudno jest je z niego zdjąć.
- Generale, czemuś mnie przykuł do murów więzienia, miast uwolnić, jako to uczyniłeś z moimi kamratami! -- wołał Bajtazar.
- Ależ Bajtazarze, wszak nie jesteś przykuty i z pewnością potrafisz sam zdjąć trzymające Cię ogniwa z pręta wystającego z murów więzienia. -- przewrotnie stwierdził generał Bajtelski, po czym dodał -- Uporaj się z tym jednak przed godziną cyfracyjną i nie dzwoń łańcuchami po nocy, gdyż w przeciwnym przypadku będę zmuszony wezwać funkcjonariuszy Cyfronicji Obywatelskiej.

Pomóż Bajtazarowi! Ponumerujmy kolejne ogniwa łańcucha liczbami 1,2,...,n. Ogniwa te możemy zakładać i zdejmować z pręta zgodnie z następującymi zasadami:

  • jednym ruchem możemy zdjąć lub założyć na pręt tylko jedno ogniwo,
  • ogniwo nr 1 można zawsze zdjąć lub założyć na pręt,
  • jeżeli ogniwa o numerach 1,...,k-1 (dla 1<=k<n) są zdjęte z pręta, a ogniwo nr k jest założone, to możemy zdjąć lub założyć ogniwo nr k+1.

Zadanie

Napisz program, który:
  • wczyta z pliku tekstowego lan.in opis bajtockiego łańcucha,
  • obliczy minimalną liczbę ruchów, które należy wykonać, aby zdjąć wszystkie ogniwa bajtockiego łańcucha z pręta,
  • zapisze wynik w pliku tekstowym lan.out.

Wejście

W pierwszym wierszu pliku tekstowego lan.in zapisano jedną dodatnią liczbę całkowitą n, 1<=n<=1 000. W drugim wierszu zapisano n liczb całkowitych o1,o2,...,on\in\0,1\ pooddzielanych pojedynczymi odstępami. Jeśli oi=1, to ogniwo nr i jest założone na pręt, a jeśli oi=0, to jest z niego zdjęte.

Wyjście

Plik tekstowy lan.out powinien zawierać jedną liczbę całkowitą, równą minimalnej liczbie ruchów potrzebnych do zdjęcia wszystkich ogniw bajtockiego łańcucha z pręta.

Przykład

Dla pliku wejściowego lan.in:
4
1 0 1 0
poprawną odpowiedzią jest plik wyjściowy lan.out
6




Wersja do druku