Problem Statement

Several students will take an exam in a narrow and long room. Each student's position is his coordinate on an axis that goes from one end of the room to the other. The students' positions are given in the int[] position. Two students can talk if the distance between them is less than or equal to maxDistance. The teacher wants to give one question to each student. He must distribute the questions such that no two students who can talk to each other will have the same question. Return the minimum number of different questions the teacher must have to make this possible.

Definition

Class:              ExamQuestions
Method:             leastAmount
Parameters:         int[], int
Returns:            int
Method signature:   int leastAmount(int[] position, int maxDistance)
(be sure your method is public)

Constraints

• position will contain between 1 and 50 elements, inclusive.
• Each element of position will be between 0 and 1000, inclusive.
• maxDistance will be between 0 and 1000, inclusive.

Examples

0)

{1, 10, 11, 4}
2
Returns: 2
The teacher can give question 0 to students 0 and 1, and question 1 to students 2 and 3.
1)

{1, 2, 3, 4, 5}
1
Returns: 2
The teacher must alternate the two questions.
2)

{4, 6, 3, 3}
0
Returns: 2
Some students may have equal positions.
3)

{12, 13, 17, 0, 5, 14, 6, 7, 16, 4}
3
Returns: 4

4)

{12, 13, 17, 0, 5, 14, 6, 7, 16, 4}
5
Returns: 5

5)

{6,8,12,14,1,18,8,5,13,9,20,12,1,22,19,19,14,0,23,6,24,18,9,16,13,9,15,23,22}
10
Returns: 15

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Google India Code Jam 2006 - Table of Contents

1. Main Page - Google India Code Jam 2006
2. Qualification Round
   • Set 1,10,13,16,25,28 :: Problem 250: ExamQuestions; Problem 1000: UnNestable
   • Set 2,9,15,20,21,27 :: Problem 250: GeneralElection; Problem 1000: UnNestable
   • Set 3,8,11,19,23,26 :: Problem 250: Sort01; Problem 1000: UnNestable
   • Set 4,7,14,18,22,29 :: Problem 250: PatternFiller; Problem 1000: PerfectNumbers
   • Set 5,6,12,17,24,30 :: Problem 250: TowerLifts; Problem 1000: PerfectNumbers
3. Elimination Round
   • Problem 250: MatrixConstructor
   • Problem 500: PalindromesAnalyzer
   • Problem 1000: VectorSet
4. Championship Round
   • Day 1, Take off to Bangalore, India (April 6, 2006)
   • Day 2, Code Jam Contest (April 7, 2006)
     • Breakfast and Google Tech Talk 1
     • The Contest Begins!!
       • Problem 300: InverseLca
       • Problem 500: ColoredDominoes
       • Problem 1000: InterestingString
     • Le Meridien and Google Tech Talk 2
     • Awards Winner announcements
     • Google Tech Talk 2 (continued) and dinner
   • Day 3, Interview with Google (April 8, 2006)
5. Links/Blogs/News