Polish version    English version  
  O olimpiadzie -> Zadania -> IX OI 2001/2002


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

Zadanie: wys
Autor: Piotr Chrząstowski-Wachtel
Wyspa

Zawody I stopnia  
Plik źródłowy: wys.??? (np. pas, c, cpp)
Plik wykonywalny: wys.exe
Plik wejściowy: wys.in
Plik wyjściowy: wys.out

W Bajtlandii postanowiono zorganizować mecz pomiędzy dwiema zwaśnionymi drużynami piłkarskimi: Linuksowcami i Mikromiękkimi. Ponieważ kibice obu drużyn znani są z wzajemnej głębokiej antypatii, należy ich ulokować w miastach możliwie najdalej od siebie oddalonych i pozwolić na oglądanie meczu tylko w telewizji. Bajtlandia jest wyspą, a wszystkie jej miasta leżą na wybrzeżu. Wzdłuż brzegów wyspy biegnie dwukierunkowa autostrada, która łączy wszystkie miasta. Z każdego miasta do każdego innego można dojechać na dwa sposoby: w kierunku zgodnym z ruchem wskazówek zegara, i w kierunku przeciwnym. Długość krótszej z tych dróg jest odległością między miastami.

Zadanie

Napisz program który:

  • wczyta z pliku tekstowego wys.in opis wyspy,
  • obliczy maksymalną odległość na jaką mogą zostać odseparowani kibice,
  • zapisze wynik w pliku tekstowym wys.out.

Wejście

W pierwszym wierszu pliku tekstowego wys.in zapisana jest jedna dodatnia liczba całkowita n, 2<=n<=50 000, oznaczająca liczbę miast znajdujących się na wyspie. W kolejnych n wierszach zapisano długości odcinków autostrady pomiędzy sąsiednimi miastami. Każdy z tych wierszy zawiera jedną dodatnią liczbę całkowitą. W wierszu o numerze i+1 zapisana jest długość odcinka autostrady pomiędzy miastem o numerze i, a miastem o numerze i+1, natomiast w wierszu o numerze n+1 zapisana jest długość drogi pomiędzy miastem n a 1. Całkowita długość autostrady nie przekracza 1 000 000 000.

Wyjście

Pierwszy i jedyny wiersz pliku tekstowego wys.out powinien zawierać jedną liczbę całkowitą oznaczającą maksymalną odległość na jaką mogą zostać odseparowani kibice.

Przykład

Dla pliku wejściowego wys.in:

5
1
2
3
4
5
poprawną odpowiedzią jest plik wyjściowy wys.out:
7



Wersja do druku