TopCoder problem "FunctionIter" used in TCCC '04 Qual. 5 (Division I Level One)



Problem Statement

    *** You may only submit a given problem once - no resubmissions will be accepted. ***



You will be given a int[] f describing a function (0-indexed). The value of the function on input k is f[k] (element k of f). To iterate a function you keep calling it on itself. For example, to iterate f 5 times on input x, you would evaluate 
     f(f(f(f(f(x))))).
Return the smallest number n larger than bound, such that iterating f n times on x evaluates to x.
 

Definition

    
Class:FunctionIter
Method:compute
Parameters:int[], int, int
Returns:int
Method signature:int compute(int[] f, int bound, int x)
(be sure your method is public)
    
 

Constraints

-f will contain between 1 and 50 elements inclusive.
-Each element of f will be between 0 and k-1 inclusive, where k is the number of elements in f.
-bound will be between 0 and 10000 inclusive.
-x will be between 0 and k-1 inclusive, where k is the number of elements in f.
-There will be a solution.
 

Examples

0)
    
{0,1,2,3,4,5}
2
4
Returns: 3
Everything is mapped to itself by f. Simply return the first value after bound.
1)
    
{1,2,3,4,5,6,0}
3
1
Returns: 7
   1->2->3->4->5->6->0->1
7 steps needed to return to 1.
2)
    
{9,9,4,4,5,6,7,18,7,10,3,4,2,8,1,3,12,3,1,1,0,0,0}
784
9
Returns: 792
3)
    
{0}
10000
0
Returns: 10001
4)
    
{0}
0
0
Returns: 1

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5004&pm=2334

Writer:

brett1479

Testers:

lbackstrom , schveiguy

Problem categories:

Simulation