Nosaukums
Ķēde (kede)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
42%

Definīcija

Ir N ķēdes gabali. i-tais ķēdes gabals satur Li ķēdes posmus. Lai savienotu vairākus gabalus kopā, patvaļīgu ķēdes posmu drīkst atliekt un pēc tam saliekt atpakaļ.

Uzrakstiet programmu, kas dotam gabalu skaitam N un posmu skaitam katrā gabalā Li nosaka, kāds mazākais posmu skaits jāatliec/jāsaliec, lai visi gabali būtu apvienoti vienā ķēdē. Ķēdei nevar būt sazarojumi, t.i., katrs posms ir savienots tieši ar diviem citiem posmiem (izņemot gala posmus, kas ir savienoti tikai ar vienu citu posmu).


Ievaddatu raksturojums

Izvaddatu pirmajā rindā dots vesels skaitlis N(2≤N ≤10000). Faila otrajā rindā doti N veseli skaitļi Li (1≤L i ≤1000000000) - ķēdes gabalu garumi. Katri divi blakus skaitļi ievaddatos ir atdalīti ar tukšumsimbolu.


Izvaddatu raksturojums

Ievaddatu vienīgajā rindā jāizvada viens vesels skaitlis - mazākais posmu skaits, kas jāatliec un pēc tam jāaizliec, lai iegūtu vienu kopīgu ķēdi.


Piezīmes

Uzdevums izmantots Ukrainas XVI.informātikas olimpiādē 2003.gadā


Paraugdati

Stdin
3
100 3 4
Stdout
2

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