Egy nagyszabású rendezvénye sok vendéget hívtak. Minden vendég előre megadta, hogy mettől meddig lesz jelen a rendezvényen. A szervezők csoportlépeken akarják megörökíteni a résztvevőket. Megbíztak egy fényképészt, hogy készítsen képeket. A fényképész azt vállalta, hogy egy-egy alkalommal T ideig marad, ha az F időpontban érkezik, akkor az F,F+1, …,F+T-1 időpontokban készíthet felvételt, de legfeljebb D alkalommal. Ha a P időpontban készíti a felvételt, akkor azon rajta lesz mindenki, aki akkor jelen van, tehát akinek az E érkezési és U távozási idejére teljesül, hogy E <= P és P<U. A szervezők azt akarják megtudni, hogy legkevesebb hány alkalommal kell kihívni a fényképészt, hogy mindenki rajta legyen legalább egy képen.
Feladat
Készíts programot, amely kiszámítja, hogy legkevesebb hány alkalommal kell kihívni a fényképészt, és azt is megadja, hogy mikor!
Bemenet
A fenykep.be
szöveges állomány első sora három egész számot tartalmaz, a vendégek N számát (1<=N<=200000), a fényképész egy alkalommal vállalt T tartózkodási idejét (1<=T<= 10000) és az egy alkalommal készíthető képek D számát (1<=D<=T). A további N sor mindegyike két egész számot tartalmaz, egy vendég E érkezési és U távozási idejét (1<=E<U<= 20000).
Kimenet
A fenykep.ki
szöveges állományba M+1 sort kell írni! Az első sorban egy egész szám legyen, az a legkisebb M szám, ahányszor ki kell hívni a fényképészt, hogy mindenki rajta legyen legalább egy fényképen! A további M sor mindegyike azokat a fényképezési időpontokat tartalmazza növekvő sorrendben (egy-egy szóközzel elválasztva), amikor az adott alkalommal fényképet kell készíteni! Több megoldás esetén bármelyik megadható.
Példa
Bemenet |
Kimenet |
8 3 2 1 3 4 6 1 4 4 8 3 6 8 12 2 4 5 9 | 2 2 4 8
|
Tesztadatok
Címkék
A feladat forrása: NTOITV 2013 2. forduló, 11-13. évfolyam
Algoritmusok: ???
megoldás