NézetNyomtat

Szarumán serege (Megoldás)
Címkék > Feladat
Elmélet > Algoritmusok > Mohó

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 \le R \le 1000, 1 \le n \le 1000$). A következő sor $n$ egész számot tartalmaz, a csapatok $x_1, x_2, \ldots,x_n$ pozícióját ($ 0 \le x_i \le 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.

Példa

army.inarmy.out
0 3 10 20 20 10 7 70 30 1 7 15 20 50 -1 -1 2 4

Tesztadatok