Egy nagyon várt film vetítésére a szervező jegyrendeléseket fogad. Minden igénylő egy jegyet igényelhet, az igénylésben megad egy ülőhely sorszámot. A feltétel az, hogy ha egy igénylő az igényében az s sorszámot adta meg, akkor el kell fogadnia olyan u sorszámú ülőhelyet, amelyre teljesül, hogy s <= u <= s+K, ahol K egy előre rögzített nemnegatív szám. A szervező feladata, hogy az igénylések közül kiválassza azt a legtöbb igényt, amelyet ki tud elégíteni. Bármely ülőhelyet legfeljebb egy igénylő kaphat meg.
Feladat
Írjunk programot, ami kiszámítja, hogy legjobb esetben hány igénylő kérését lehet kielégíteni! A program adjon is meg egy megfelelő jegykiosztást!
Bemenet
A mozi.be szöveges állomány első sorában három egész szám van, az ülőhelyek M száma (1 <= M <= 3000), az igények N száma
(1 <= N <= 10000) és a K (0 <= K <= 100) értéke. Az ülőhelyeket az 1,...,M számokkal azonosítjuk. A második sor pontosan N egész számot tartalmaz (egy-egy szóközzel elválasztva). Az i-edik szám annak az ülőhelynek a sorszáma, amelyet az i-edik
igénylő szeretne megkapni.
Kimenet
A mozi.ki szöveges állomány első sora egy L egész számot tartalmazzon, a legtöbb kielégíthető igény számát! A következő L sor egy megfelelő jegykiosztást tartalmazzon. Minden sorban két egész szám legyen egy szóközzel elválasztva, az első szám egy igénylő sorszáma, a második pedig annak az ülőhelynek a sorszáma legyen, amelyiket ez az igénylő kap! A kiírás sorrendje tetszőleges. Több megoldás esetén bármelyik megadható.
Példa
| Bemenet |
Kimenet |
5 7 1
4 2 1 3 2 4 5
|
5
3 1
2 2
5 3
4 4
1 5
|
Tesztadatok
Címkék
A feladat forrása: NTOITV 2013-2014, 2. forduló, 9-10. évfolyam
Algoritmusok:
| 
2004-2016 BDG algoritmus szakkör