apraksts uzdevumi suutiit jauns statuss rezultati helps apraksts

kede Ķēde 1 sek.


 Uzdevums

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).

 
 Ievaddati

Teksta faila kede.dat 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.

 
 Izvaddati

Teksta faila kede.rez 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.

 
 Piemērs

kede.datkede.rez
3
100 3 4
2

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

Drukāšanai

 

Copyright © 2001 Girts Folkmanis, LIIS