Kemence
(Megoldás)
Elmélet > Algoritmusok > Dinamikus programozás
Címkék > Feladat
Versenyek > Nemes Tihamér OKSzTV > 2001 > Döntő > 11-13. osztály
Elmélet > Algoritmusok > Dinamikus programozás
Címkék > Feladat
Versenyek > Nemes Tihamér OKSzTV > 2001 > Döntő > 11-13. osztály
Kemence
A feladat szövege
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:
Készíts olyan 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 KEMENCE.BE állomány 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:
A KEMENCE.KI állomány első sorába 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
| Input | Output |
| 6 10 3 10 2 12 7 20 5 15 3 11 2 16 | 46 1 1 2 3 4 6 |