Cserép korsók kiégetésére szakosodott vállalkozó egy kemencét üzemeltet.
Az égetésre érkező korsókat az érkezés sorrendjében kell a kemencében
kiégetni. Egy menetben legfeljebb K korsó rakható a kemencébe. Minden
korsóra adott a minimális és maximális égetési idő, percben kifejezve.
Továbbá minden korsóra adott egy H határidő, ami azt jelenti, hogy a
munka megkezdésétől számítva, a H időpontig el kell készülnie a
kiégetésnek. Figyelembe kell venni, hogy egy menet előkészítése 1 percet
vesz igénybe.
Feladat
Készíts programot, amely kiszámítja, hogy a követelmények betartásával
legkevesebb mennyi idő alatt lehet kiégetni az összes korsót és meg is
ad egy helyes beosztást.
Bemenet
Az első sorban a korsók N száma és a kemence K kapacitása van.
(1<=N<=10000, 1<=K<=100) A következő N sor mindegyike három
számot tartalmaz: a minimális és maximális égetési idő, majd a
határidő. (1<=min<=max<=1000)
Kimenet
Az első sorba a szükséges égetési időt és a szükséges menetek számát kell írni.
Ezután annyi sor következik, amennyi a szükséges menetek száma, és minden sorba
a megfelelő menetben kiégetett első és utolsó korsó sorszáma kerül.
Példa
Bemenet |
Kimenet |
4 3 1 2 4 2 3 3 3 4 8 1 2 9
| 9 3 1 2 3 3 4 4
|
Tesztadatok
Címkék
A feladat forrása: NTOITV 2011, 11-13. évfolyam, 3. forduló
Algoritmusok:
megoldás |