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 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 kilométertől az kilométerig vállalja a futást, akkor minden olyan futó át tudja venni tőle a lángot, aki olyan kilométertől vállalja a
futást, hogy .
Feladat
Írj programot (STAFETA.PAS, ...), amely kiszámítja, hogy legkevesebb hány futó kell
ahhoz, hogy a láng eljusson a cél városig.
Bemenet
A STAFETA.BE szöveges állomány első sorában két egész szám található: a két város távolsága és a jelentkezett futók száma . A további sor mindegyikében két egész szám van és () ami azt jelenti, hogy egy futó az -edik kilométertől az -edik kilométerig vállalja a láng továbbítását. A futókat a sorszámukkal azonosítjuk, a bemenet -edik sorában a -edik futó adata van. Feltételezhetjük, hogy a láng eljuttatható a cél városig a jelentkezett futókkal.
Kimenet
A STAFETA.KI szöveges állomány első sorába a láng célba juttatásához minimálisan
szükséges futók számát kell írni. A második sor pontosan 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 -edik futó a -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
