Programozás‎ > ‎Feladatok‎ > ‎

Staféta

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