A porcelángyár égetőkemencéjéhez futószalagon érkeznek az égetésre váró
tárgyak. Minden tárgynak ismert a súlya és a kiégetéséhez minimálisan
szükséges idő. Az égetésre váró tárgyakat az érkezésük sorrendjében kell
kiégetni. Egyszerre több tárgyat is rakhatunk a kemencébe, az
összsúlyuk azonban nem haladhatja meg a kemence kapacitását. Az égetési
idő egy menetben mindig a kemencébe rakott tárgyak minimális égetési
idejének a maximuma kell legyen.
Feladat
Írjunk programot, amely kiszámítja, hogy legkevesebb mennyi idő kell az összes tárgy
kiégetéséhez, továbbá megadja azt is, hogy ezen idő eléréséhez mely
tárgyakat kell egy-egy menetben a kemencében együtt égetni.
Bemenet
A bemenet első sora két egész számot tartalmaz; a tárgyak N
(1<=N<=10000) számát és a kemence K (1<=K<=1000)
kapacitását. A következő N sor mindegyike két egész számot tartalmaz;
egy tárgy S (1<=S<=1000) súlyát és E (1<=E<=100) minimális
égetési idejét.
Kimenet
Az első sorba az összes tárgy kiégetéshez minimálisan szükséges időt kell írni. A
következő sorok mindegyikébe két egész számot, I-t és J-t kell írni egy
szóközzel elválasztva, I az első, J pedig az utolsó tárgy sorszáma,
amelyek egyszerre kerülnek a kemencébe.
Példa
Bemenet |
Kimenet |
6 10 3 10 2 12 7 20 5 15 3 11 2 16
| 46 1 1 2 3 4 6
|
Tesztadatok
Címkék
A feladat forrása: NTOITV 2001, 3. forduló, 11-13. évfolyam
Algoritmusok: dinamikus programozás
|