NézetNyomtat

Munka (Megoldás)
Elmélet > Algoritmusok > Dinamikus programozás
Címkék > Feladat

Munka

Egy vállalkozó két azonos munkagépet üzemeltet, amelyeken speciális alkatrészeket gyárt. Sok megrendelést kapott alkatrészek gyártására. A megrendelésben különböző alkatrészek szerepelnek, de ismert, hogy az egyes alkatrészek legyártása mennyi időt igényel (percben kifejezve). A gépek folyamatosan dolgoznak. A vállalkozó el akarja osztani az alkatrészeket a két gép között, hogy a lehető legkorábban befejeződjön a legyártásuk, tehát ha az első gép a neki kiosztott alkatrészeket $T_1$, a második gép $T_2$ idő alatt gyártja le, akkor $\mbox{max}( T_1,T_2)$ a lehető legkisebb legyen.

Feladat

Készíts programot (MUNKA.PAS, ...), amely kiszámítja, hogy legkevesebb mennyi idő alatt tudja a két gép legyártani az összes alkatrészt, és meg is ad egy megfelelő beosztást!

Bemenet

A MUNKA.BE szöveges állomány első sorában az alkatrészek $(2\leq N\leq 2000)$ száma van. A második sor pontosan N egész számot tartalmaz egy-egy szóközzel elválasztva, a legyártandó alkatrészek gyártási idejét, ami 1 és 50 közötti érték.

Kimenet

A MUNKA.KI szöveges állomány első sora egyetlen egész számot tartalmazzon, azt a legkisebb $T$ időt, amely alatt a két gép le tudja gyártani az összes alkatrészt! A második sor azon alkatrészek sorszámát tartalmazza (tetszőleges sorrendben, egy-egy szóközzel elválasztva), amelyeket az első, a harmadik sor pedig azokat, amelyeket a második gép gyárt le. Több megoldás esetén bármelyik megadható.

Példa

MUNKA.BEMUNKA.KI
9
7 12 5 21 6 9 31 4 12
54
2 3 5 7
1 4 6 8 9

Tesztadatok