Szarumán hadserege egyenes úton halad Vasudvardból a Helm Szurdok felé. A csapatok mozgását látó kövek - palantírok - segítségével követi a Fehér Varázsló. Minden palantír R egység távolságba "lát", és a palantírok nem tudnak magukban lebegni, mindegyiket valamelyik csapat viszi magával.
Feladat
Írj programot, ami segít Szarumánnak elfoglalni Középföldét, megadva a minimális számú palantírt, amivel a sereg összes csapata látható egy adott pillanatban.
Bemenet
A bemenet több tesztesetet tartalmaz.
Minden teszteset első sora a palantírok R "látótávolságát" és a csapatok N számát adja meg ( 0 <= R <= 1000,1 <= N <= 1000).
A következő sor N egész számot tartalmaz, a csapatok x1, x2,…, xN pozícióját ( 0 <= xi <= 1000 ). Az input végét egy "-1 -1" sor jelzi.
Kimenet
Minden kérdéshez írjuk ki, hogy legkevesebb hány palantír kell ahhoz, hogy Szarumán minden csapatot láthasson.Az első sorba
Példa
Bemenet |
Kimenet |
0 3
10 20 20
10 7
70 30 1 7 15 20 50
-1 -1
|
2 4
|
Tesztadatok
Címkék
A feladat forrása: ACM North Central America Regional Contest 2002
Algoritmusok: rendezés, mohó algoritmus
|