Nosaukums
Sliežu ceļi (celi)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
83%

Definīcija

Dzelzceļa līnijā ir N stacijas, kas sanumurētas ar naturāliem skaitļiem no 1 līdz N pēc kārtas. Ir zināms attālums kilometros starp katrām divām blakusesošām stacijām. Pagaidām dzelzceļa līnijā ir tikai viens sliežu ceļš, bet ir nolemts sākt būvēt dublējošos sliežu ceļus tā, lai no katras stacijas vismaz uz vienu no kaimiņu stacijām būtu divi paralēli sliežu ceļi un lai dublējošo sliežu ceļu kopgarums būtu pēc iespējas mazāks.

Piemēram, dzelzceļa līnijā var būt piecas stacijas un attālums starp blakusesošām stacijām tāds, kā redzams zīmējumā:

Tad dublējošie sliežu ceļi jābūvē starp 1. un 2., 3. un 4., 4. un 5. staciju:

Šajā gadījumā dublējošo sliežu ceļu kopgarums ir 17 kilometri.

Uzrakstiet programmu, kas dotam staciju skaitam un attālumam starp blakusesošām stacijām aprēķina īsāko iespējamo dublējošo sliežu ceļu kopgarumu!

 


Ievaddatu raksturojums

Teksta datnes celi.dat pirmajā rindā dots naturāls skaitlis N (1 < N ≤ 1 000 000). Katrā no nākamajām N-1 datnes rindām dots viens naturāls skaitlis, kura vērtība nepārsniedz 1000, - attālums starp divām blakusesošām stacijām. Katram i (2 ≤ i ≤ N) attālums starp (i-1)-o un i-to staciju ir dots datnes i-tajā rindā.

 


Izvaddatu raksturojums

Teksta datnes celi.rez vienīgajā rindā jāizvada viens naturāls skaitlis - īsākā iespējamā dublējošā sliežu ceļa kopgarums.

 


Piezīmes

celi.dat celi.rez  
5
7
13
4
6
17
Atbilst uzdevuma formulējumā dotajam piemēram.
     
celi.dat celi.rez  
4
7
1
13
20
 

 
Uzdevums izmantots Latvijas 22. informātikas olimpiādē 2009. gadā.


Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.