Egy fazekas műhelyében sorban várakoznak a kiégetésre váró tárgyak.
Minden tárgyról tudjuk, hogy mennyi az a legkevesebb idő, ami a
kiégetéshez kell. 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, azonban
legfeljebb annyit, amennyi a kemence adott kapacitása. 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 bemeneti á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<=100) kapacitását.
A következő N sor mindegyike egy pozitív egész számot tartalmaz; a
tárgy minimális égetési idejét, ami nem nagyobb, mint 200.
Kimenet
Az első sorba az összes tárgy kiégetéséhez 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 |
7 3
10
8
20
25
30
12
40 | 75 1 2 3 4 5 7
|
Tesztadatok
Címkék
A feladat forrása: NTOITV 2001, 3. forduló, 9-10. évfolyam
Algoritmusok: dinamikus programozása
|