Programozás‎ > ‎Feladatok‎ > ‎

Kemence (2011)

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