Programozás‎ > ‎Feladatok‎ > ‎

Fazekas

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