Az olimpiai lángot egy kiindulási városból a cél városba kell eljuttatni. A két város távolsága K
kilométer. Sok futó jelentkezett, mindegyikről tudjuk, hogy hányadik
kilométertől hányadik kilométerig vállalja a futást. Ha egy futó az x kilométertől az y kilométerig vállalja a futást, akkor minden olyan futó át tudja venni tőle a lángot, aki olyan z kilométertől vállalja a
futást, hogy x<=z<=y.
Feladat
Írjunk programot, amely kiszámítja, hogy legkevesebb hány futó kell
ahhoz, hogy a láng eljusson a cél városig.
Bemenet
A bemenet szöveges állomány első sorában két egész szám található: a két város távolsága (10<=K<=1000) és a jelentkezett futók száma (2<=N<=20000). A további N sor mindegyikében két egész szám van I és E (0<=I<E<=K) ami azt jelenti, hogy egy futó az I-edik kilométertől az E-edik kilométerig vállalja a láng továbbítását. A futókat a sorszámukkal azonosítjuk, a bemenet j+1-edik sorában a j-edik futó adata van. (Tehát a futókat 1-től számozzuk.) Feltételezhetjük, hogy a láng eljuttatható a cél városig a jelentkezett futókkal.
Kimenet
A kimeneti szöveges állomány első sorába a láng célba juttatásához minimálisan
szükséges futók M számát kell írni. A második sor pontosan M
számot tartalmazzon (egy-egy szóközzel elválasztva), azon futók
sorszámait, akik teljesítik a feladatot. Tehát a felsorolásban a j-edik futó a j+1-edik futónak adja át a lángot. Több megoldás esetén bármelyik megadható.
Példa
STAFETA.BE
|
STAFETA.KI |
40 7 2 21 25 35 20 34 0 10 5 18 3 7 34 40
| 4 4 1 3 7
|
Tesztadatok
Címkék
A feladat forrása: NTOITV 2008/2009 III. kategória, 2. forduló
Algoritmusok: mohó algoritmus
|