Programozás‎ > ‎Feladatok‎ > ‎

Szarumán serege

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