Programozás‎ > ‎Feladatok‎ > ‎

Csoportkép

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