Problem Statement

We make cardboard boxes. We manufacture a variety of sizes and are concerned that storing them and transporting them will be a problem unless we can nest them into a reasonable number of nested stacks. The boxes are rectangular, but they are open at the top so their heights don't matter. If we call the smaller horizontal dimension of a box its width and the other dimension its length, a box can be nested in another box if its width is less than the other's width, and its length is less than the other's length. No diagonal nesting is allowed.

We have automated the manufacturing process so that random sized boxes are produced. We specify values a, p, and n and the machine produces n boxes with dimensions:

     (a,a^2)  (a^3,a^4)  (a^5,a^6)  ...  (a^(2n-1),a^(2n))

where a^j denotes (a to the j power) mod p.

Create a class UnNestable that contains a method maxCount that is given the positive integral values a, p, and n and that returns the size of the largest unnestable collection of boxes, where a collection is unnestable if no two boxes from the collection can be nested.

The sequence of boxes can be generated by

    int rv=1;
    for(int i=0; i


Definition
Class:              UnNestable
Method:             maxCount
Parameters:         int, int, int
Returns:            int
Method signature:   int maxCount(int a, int p, int n)
(be sure your method is public)


Notes
The sequence may cycle, resulting in many boxes of the same dimensions. Duplicate boxes do count in the size of an unnestable collection

Constraints

p is between 2 and 2,000,000,000, inclusive.
a is between 1 and p-1, inclusive.
No power of a is divisible by p.
a*p is less than or equal to 2,000,000,000
n is between 1 and 10,000 inclusive


Examples
0)

10
15
3
Returns: 3
The random generator produces 10, (10*10)%15=10, 10*10%15=10, ... so the The three boxes are (10,10), (10,10), and (10,10). The entire collection is unnestable.
1)

10
17
4
Returns: 2
The sequence is 10, 100%17=15, 150%17=14, 140%17=4, 40%17=6, ... so the 4 boxes are (10, 15), (4, 14), (6, 9) and (5, 16). The non-nesting pairs are (10, 15) with (5, 16), (4, 14) with (6, 9), and (6, 9) with (5, 16). No collection of 3 of these boxes is pairwise unnestable.
2)

3
1000
3
Returns: 1
The boxes are (3,9), (27,81), and (243,729). The first one is nestable in both the others, and the second one is nestable in the third one. So there is no way to choose 2 of them which are unnestable. Of course, any collection of size one has the property that no two boxes from the collection can be nested.
3)

3
104729
10000
Returns: 9


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

	
Main Page - Google India Code Jam 2006
	
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
	

	
Elimination Round
	

		
Problem 250: MatrixConstructor
		
Problem 500: PalindromesAnalyzer
		
Problem 1000: VectorSet
	

	
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)
	
	
Links/Blogs/News