Informatika gyűjtemény

Egy szinttel feljebb Fazekas

2004050607080910

NézetNyomtat

Fazekas

A feladat szövege

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 (FAZEKAS.PAS vagy FAZEKAS.C), 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 FAZEKAS.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<=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:

A FAZEKAS.KI állomány első sorába 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

InputOutput
7 3 10 8 20 25 30 12 40 75 1 2 3 45 7

Tesztadatok