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.
Feladat
Í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!
Bemenet
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.
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
Bemenet |
Kimenet |
9
7 12 5 21 6 9 31 4 12
|
54
2 3 5 7
1 4 6 8 9
|
Tesztadatok
Címkék
A feladat forrása: NTOITV 2009, 2. forduló, 11-13. évfolyam
Algoritmusok: dinamikus programozás
megoldás |