Very tough C++ exam question!!HELP!!!!

[DarkSatan]

I just found this tough question in the last year Q Paper of this exam...I dont know how to take that type of input,leave alone the logic...Can any1 help me with this program, plz... :

Question 1 Vogon zoo

On the icy planet Zorg, the Vogons are putting together a zoo. One cage will house a
collection of Kubudu dragons. Unlike the limited number of blood types found in other
creatures, Kubudu dragons have a large variety of blood types. Each dragon's blood type is fixed when it is born and is given by a positive integer.

These blood types determine how the dragons interact with each other. Two dragons
whose blood types are close to each other will quickly start fighting and eventually destroy each other. At any given time, there is a threshold K such that it is safe to put two Kubudu dragons in the same cage only if their blood types differ by K or more.

A batch of freshly hatched Kubudu dragons has arrived. Each dragon has had its blood
tested and is tagged with its blood type. The Vogon zookeeper would like to determine the size of the largest collection of dragons from this batch that can safely be placed in a single cage. Given the dragons' fighting tendencies, this means that for each pair of dragons in the cage, their blood types should differ by at least K.

For instance, suppose that K is 3 and there are 12 Kubudu dragons whose blood types
are 1, 5, 6, 1, 8, 3, 12, 2, 13, 7, 9 and 11. From this batch, the maximum number of dragons that can be placed safely in the same cage is 4.For example, the dragons with blood types
6, 12, 2 and 9.

You will be given the blood types of N Kubudu dragons and the threshold K. Your task
is to compute the size of the largest group of dragons from this collection that can safely be
placed in the same cage.
Input format
The rst line of input has two space separated integers N and K, where N is the number
of Kubudu dragons and K is the threshold below which they ght, as described above. The
second line of input consists of N space separated integers, the blood types of the N dragons.
Output format
A single integer, the size of the largest collection of dragons that can be safely placed in the
same cage.
Test data
In all cases, 1 < N < 106. In 30% of the inputs, 1 < N < 5000. The blood types of the
dragons lie in the range 1 to 107.

Example
Sample input
4
6 0 3 -1
7 4 2 4
-3 3 -2 8
13 10 -1 -4

Sample output
56

Note: Your program should not print anything other than what is specified in the output
format. Please remove all diagnostic print statements before making your final submission.
A program with extraneous output will be treated as incorrect!

[Greywolf333]

Please explain: "In all cases, 1 < N < 106. In 30% of the inputs, 1 < N < 5000."
is this a contradiction?

also please explain: "The first line of input has two space separated integers N and K" But then in the sample input the first line has only "4".

[csurfer]

This is definitely not an exam question its a question picked up from some coding competition or as the "Note:" section says that its an assignment as it speaks of the submission and the criteria to be met before the submission.

Anyways these type of question normally follow a format as to number of test cases followed by important data of the question(here N and K) and then the detailed data(Here the blood group).As :

2
4 2
1 1 4 7
6 3
1 4 8 12 16 20

Here it means that it has two test cases as the first line signifies TC's.
Then the test cases follow where first line of TC has N K format then the N dragons blood group in the next line.So on and so forth for all the other test cases to follow. Now you know how to take inputs come up with your algorithm to solve it :)

[csurfer]

This is definitely not an exam question its a question picked up from some coding competition or as the "Note:" section says that its an assignment as it speaks of the submission and the criteria to be met before the submission.

Anyways these type of question normally follow a format as to number of test cases followed by important data of the question(here N and K) and then the detailed data(Here the blood group).As :

2
4 2
1 1 4 7
6 3
1 4 8 12 16 20

Here it means that it has two test cases as the first line signifies TC's.
Then the test cases follow where first line of TC has N K format then the N dragons blood group in the next line.So on and so forth for all the other test cases to follow. Now you know how to take inputs come up with your algorithm to solve it :)