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 T1, a második gép T2 idő alatt gyártja le, akkor max(T1, T2) a lehető legkisebb legyen. 

Írjunk programot, 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!

A MUNKA.BE szöveges állomány első sorában az alkatrészek (2 <= N <= 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. 

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ó.

Bemenet	Kimenet
9 7 12 5 21 6 9 31 4 12	54 2 3 5 7 1 4 6 8 9

A feladat forrása: NTOITV 2009, 2. forduló, 11-13. évfolyam

Algoritmusok: dinamikus programozás

megoldás