TopCoder problem "PScores" used in TCO06 Qual 5/6/12 (Division I Level One)



Problem Statement

    A game is played as follows. The player is given a number p (his current p-value) between 0 and N-1 inclusive, where N is the number of elements in nexts. The following steps are then repeated until the game ends:
  1. Look at nexts[p]. If the player has already had nexts[p] earlier in the game, the game is over, and his score is p.
  2. Otherwise, the current p-value is changed to nexts[p].
Return the number of distinct initial p-values that would result in the given final score.
 

Definition

    
Class:PScores
Method:howMany
Parameters:int[], int
Returns:int
Method signature:int howMany(int[] nexts, int score)
(be sure your method is public)
    
 

Constraints

-nexts will contain between 1 and 50 elements inclusive.
-Each element of nexts will be between 0 and N-1 inclusive, where N is the number of elements in nexts.
-score will be between 0 and N-1 inclusive, where N is the number of elements in nexts.
 

Examples

0)
    
{0,1}
0
Returns: 1
Each player begins the game, and then has no place to go, so the game ends. Only the player that initially receives 0 has score 0.
1)
    
{1,2,3,4,5,6,7,8,9,0}
3
Returns: 1
The player who starts with 4 will travel all the way around, and finally end up with score 3.
2)
    
{0,0,0,0,0,0,0,0,0,0,0,0,0,0}
0
Returns: 14
The score 0 is popular.
3)
    
{2,2,0}
0
Returns: 2
Players that initially receive 1 or 2 will end up with score 0.
4)
    
{0,11,25,29,9,18,0,3,18,19,6,23,25,6,3,9,2,26,10,4,14,10,20,23,26,23,6,16,12,24}
23
Returns: 9

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6107

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9901&pm=6107

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom , Olexiy

Problem categories:

Simple Search, Iteration, Simulation