Destroy the Enemy

Problem code: CRAFT02

A war is going on between two countries. You are the military head and got information from intelligence about the positions of the enemy troops. You have the missiles and when they hit the target they create a destruction in a region of radius D. Assume that the y coordinate of all the troops is same and have different x co-ordinates as x1,x2, xi, xn. Also assume that all troops are in the range of our missile and the missile can only be targeted to one of the troops. You need to destruct the enemy force by using minimum number of missiles.

Input

The input test file will contain multiple cases. Each test case begins with a single line containing an integer D, the maximum effective range of all missiles (where 0 D 100), and an integer n, the number of troops of the enemy (where 1 n 100). The next line contains n integers, indicating the positions x1,x2, xi, xn of each troop (where 0 xi 100). The end-of-input is marked by a test case with D = n = 1.

Output

For each test case, print a single integer indicating the minimum number of missiles needed.

Example

Input:
0 3
10 20 20
10 7
70 30 1 7 15 20 50
-1 -1


Output:
2
4

Date: 2010-03-04
Time limit: 30s
Source limit: 50000
Languages: C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK JS


Comments

can anybody tell something

cybersharp @ 10 Mar 2010 03:43 PM

can anybody tell something about this competition??

@ Craft 2010 :::: CRAFTALG

vish @ 10 Mar 2010 10:19 PM

@ Craft 2010 :::: CRAFTALG

where to register for this contest ??

its a practice contest or real contest???

can any body elloborate the

dabbcomputers @ 10 Mar 2010 10:26 PM

can any body elloborate the test cases pls...

is the range of missile and

dabbcomputers @ 10 Mar 2010 11:22 PM

is the range of missile and destruction radius both are same??

input ends with 1 or -1 ?

dejavu @ 11 Mar 2010 01:43 AM

input ends with 1 or -1 ?

This is a real contest and is

amanatadmin @ 11 Mar 2010 10:37 AM

This is a real contest and is a part of Technical fest NIMBUS '10 of NIT Hamirpur.

You can submit your solutions direcly if you have an account here

inputs ends with -1 -1

amanatadmin @ 11 Mar 2010 10:38 AM

inputs ends with

-1 -1

NO need to worry about the

amanatadmin @ 11 Mar 2010 10:39 AM

NO need to worry about the range as all are within the range as mentioned in the question

can anyone explain the first

gaurav17 @ 11 Mar 2010 02:50 PM

can anyone explain the first test case with d=0?

what are x1, x2, xi, xn??

mcsharma1990 @ 11 Mar 2010 05:41 PM

what are x1, x2, xi, xn??

when you say input end with

alok @ 11 Mar 2010 08:11 PM
when you say input end with D=n=-1, is it possible that our submission will be tested against cases with D= -1 and n!= -1 ?

Or vice-versa. Or is it

alok @ 11 Mar 2010 08:15 PM

Or vice-versa. Or is it mandatory to put both n=-1 and d= -1 togather because if not, then are you testing for cases like d=-1, n=3 ?

@Lucky: No it is clearly

amanatadmin @ 12 Mar 2010 01:13 AM

@Lucky: No it is clearly mentioned that the input ends with -1 -1

@Mahesh Chandra

amanatadmin @ 12 Mar 2010 01:15 AM

@Mahesh Chandra Sharma:x1,x2...xi....xn are the assumed x co-ordinates

can anyone explain the test

rohitkg @ 12 Mar 2010 02:00 AM

can anyone explain the test cases, please...

hmmmm

mohan krishna @ 13 Mar 2010 06:23 PM

hmmmm

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions