Prihlásenie Registrácia  

A - Elektroinštalácia

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Peťo sa rozhodol kúpiť si byt. Nemal dosť peňazí na kúpu bytu v novostavbe, preto kúpil panelákový byt v pôvodnom stave. Zatiaľ má kde bývať (u rodičov), tak sa rozhodol, že si ho prerobí svojpomocne, aj keď to bude dlhšie trvať. Pri dôkladnej obhliadke zistil, že niektoré zásuvky nefungujú a elektrické vedenie je dvojžilové (dnešným normám už nevyhovujúce) a hliníkové (teraz sa používa medené). Rozhodol sa teda pre výmenu kabeláže. Pripravil si projekt, kde chce mať zásuvky a odmeral si jednotlivé vzdialenosti (medzi zásuvkami, ako aj k rozvodnej skrinke). V elektrickej sieti sa môžu káble rozvetvovať, ale po rozvetvení sa už nemôžu ďalej spojiť (uzavrel by sa okruh a nastal skrat). Odmeral si iba tie úseky, do ktorých bude dávať kábel. Potreboval by zistiť, koľko káblu mu treba objednať. Jeho strýko Juraj mu poradil, nech si každú izbu napojí na zvlášť istič (všetky ističe musia byť v rozvodnej skrini). To ale znamená, že na niektorom úseku bude viac káblov vedľa seba. Takže Peťo potrebuje vedieť aj najviac koľko káblov mu bude uložených vedľa seba, aby vedel kúpiť dostatočne široké lišty.

projekt elektroinštalácie

Úloha

Máte hotový projekt - korektný popis rozvetvenia od rozvodnej skrine ku všetkým zásuvkám. Pre daný počet zásuviek v jednotlivých izbách a namerané vzdialenosti vypočítajte koľko káblov bude najviac uložených vedľa seba a celkovú dĺžku kábla potrebného na zapojenie bytu.

Vstup

V prvom riadku sú počty zásuviek v jednotlivých izbách (rozvodná skriňa nepatrí do žiadnej izby). Počet čísel v riadku určuje počet izieb. Zásuvky sú očíslované postupne po jednotlivých izbách, pričom číslo 1 je rozvodná skriňa. Napríklad riadok 1 2 3 znamená:
  • rozvodná skrina je označená číslom 1
  • v prvej izbe je jedna zásuvka - číslo 2
  • v druhej izbe sú dve zásuvky - číslo 3, 4
  • v tretej izbe sú tri zásuvky - čísla 5, 6, 7
Nasleduje popis úsekov (tých je taký istý počet ako počet zásuviek v izbách), pričom v každom riadku sú tri čísla 1 ≤ Z1, Z2 ≤ 100 (čísla zásuviek) a 1 ≤ D ≤ 1000 (vzdialenosť medzi nimi).

Výstup

Jeden riadok obsahujúci dve čísla K (maximálny počet káblov) a C (celková dĺžka kábla).

Príklad 1

Vstup:

2 2
1 2 100
2 3 50
3 4 40
3 5 40

Výstup:

2 380

Príklad 2

Vstup:

1 1 1 2
1 2 1000
2 3 100
2 4 100
3 5 100
4 6 100

Výstup:

4 4600