Uvođenje telefona u ulicu
| vreme | memorija | ulaz | izlaz |
|---|---|---|---|
| 1 s | 1000 Mb | standardni izlaz | standardni ulaz |
U naselju ima n zgrada, raspoređenih po pravom putu s jedne strane na jednakim (jediničnim) rastojanjima. U naselje se uvodi telefonska veza. U nizu T od n elemenata, navedeno je koliko priključaka treba uvesti u svaku zgradu. Svaki telefon mora biti vezan sa centralom posebnim provodnikom. Centrala će biti postavljena u neku od postojećih zgrada. Odrediti kolika je minimalna zbirna dužina provodnika od centrale do svih priključaka.
U prvom redu broj zgrada n, manji ili jednak milion. U drugom redu n celih nenegativnih brojeva T[i], manjih ili jednakih 1000, razdvojenih razmakom.
Jedan broj, tražena minimalna zbirna dužina provodnika.
6
3 5 1 6 2 4
30
Minimalna zbirna dužina provodnika se dobija kada se centrala smesti u četvrtu zgradu sleva, a tada je potrebno 3∙3 + 2∙5 + 1∙1 + 1∙2 + 2∙4 = 30 dužinskih jedinica provodnika.
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.