Рутер
vreme | memorija | ulaz | izlaz |
---|---|---|---|
0,1 s | 64 Mb | standardni izlaz | standardni ulaz |
Дуж једне улице су равномерно распоређене зграде (растојање између сваке две суседне је једнако). За сваку зграду је познат број корисника које нови добављач интернета треба да повеже. Одредити у коју од зграда треба поставити рутер тако да би укупна дужина оптичких каблова којим се сваки од корисника повезује са рутером била минимална (рачунати само дужину каблова од зграде до зграде и занемарити дужине унутар зграда).
Улаз
У првом реду стандардног улаза налази се број n (1≤n≤105), а у наредном n природних бројева раздвојених размацима који представљају број корисника у свакој од n зграда.
Излаз
На стандардни излаз исписати минималну дужину каблова.
Пример
Улаз
6 3 5 1 6 2 4
Излаз
30
Рутер треба поставити у четврту зграду слева и дужина каблова је тада једнака 3⋅3+2⋅5+1⋅1+1⋅2+2⋅4=30.
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.