Dělení nosníků

Úkolem je realizovat program, který bude počítat optimální dělení ocelových nosníků.

Předpokládáme, že potřebujeme vyrobit nosníky zadaných délek. Požadované délky jsou programu předané jako seznam celých čísel. Máme k dispozici dlouhý ocelový nosník, jeho délka je rovna součtu jednotlivých požadovaných délek. Dlouhý nosník je možné rozdělit na dva menší, při dělení nedochází ke ztrátě materiálu (součet délek rozděleného nosníku se rovná délce původní). Cena za dělení je ale daná délkou děleného nosníku. Úkolem je vypočítat, jak nosník rozdělit na zadané délky za co nejnižší cenu.

Vstupem programu je seznam požadovaných délek rozdělených nosníků. Požadované délky jsou celá kladná čísla. Zadávání skončí dosažením konce vstupu (EOF). Víte, že seznam obsahuje nejvýše 500000 prvků.

Výstupem programu je nalezená nejnižší cena za rozdělení nosníku na požadované délky.

Program musí kontrolovat správnost vstupních dat. Pokud je detekovaný nesprávný vstup, program zobrazí chybové hlášení a ukončí se. Za chybu je považováno:

    prázdný seznam požadovaných délek,
    seznam požadovaných délek je delší než 500000 hodnot,
    nečíselné, nulové nebo záporné délky nosníku.

Váš program bude spouštěn v omezeném testovacím prostředí. Je omezen dobou běhu (limit je vidět v logu referenčního řešení) a dále je omezena i velikost dostupné paměti. V závislosti na zvoleném algoritmu může být úloha výpočetně náročnější. Správně implementovaný naivní algoritmus projde všemi povinnými a nepovinnými testy, tedy bude hodnocen nominálním výsledkem 100 %. Pokud se rozhodnete implementovat algoritmus efektivnější, který pracuje rychle i pro větší objem vstupních dat, můžete získat body navíc za bonusové testy. V bonusových testech jsou na vstupu dlouhé seznamy délek. Paměťový limit s rezervou postačuje pro uložení vstupního seznamu.
Ukázka práce programu:

Zadejte delky:
1 2 3 4 5
Cena za deleni: 33

Zadejte delky:
3 6 4 7
Cena za deleni: 40

Zadejte delky:
1 1 1 1 1 1 1 1 1 1 1 1
Cena za deleni: 44

Zadejte delky:
2 9 8 124 31 71
45 21 3 1 9
Cena za deleni: 849

Zadejte delky:
178
Cena za deleni: 0

Zadejte delky:
13 -8
Nespravny vstup.

Poznámky:

    Ukázkové běhy zachycují očekávané výpisy Vašeho programu (tučné písmo) a vstupy zadané uživatelem (základní písmo). Zvýraznění tučným písmem je použité pouze zde na stránce zadání, aby byl výpis lépe čitelný. Váš program má za úkol pouze zobrazit text bez zvýrazňování (bez HTML markupu).
    Znak odřádkování (\n) je i za poslední řádkou výstupu (i za případným chybovým hlášením).
    Pro reprezentaci délek a cen v povinných a nepovinných testech postačuje datový typ int. Pro zvládnutí bonusového testu je potřeba zpracovávat velké ceny, tedy použít větší datový typ (např. long long).
    Vstup programu je omezen na seznam délky nejvýše 500000 prvků. Nemusíte se zabývat dynamickou alokací, vyhoví i staticky alokované datové struktury. V této úloze není hodnocena efektivita využívání paměti.
    Slovní popis struktury platných vstupních dat není zcela exaktní. Proto připojujeme i formální popis vstupního jazyka v EBNF:

         input      ::= { whiteSpace } { length { whiteSpace } }
         length     ::= integer
         whiteSpace ::= ' ' | '\t' | '\n' | '\r'
         integer    ::= digit { digit }
         digit      ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'