TopCoder problem "RoundAboutCircle" used in SRM 392 (Division I Level Two)



Problem Statement

    

N cells are located around a circle. Cells are numbered 1 through N in the clockwise direction.

Initially, you can place a token into any one of these cells.

In each turn, you look at the number of the cell containing the token and you calculate s, the sum of the digits in that number. You then move the token s cells clockwise.

This process continues until you move the token into a cell that already contained the token before. Your score is the number of cells that were visited by the token at least once during the process (including the initial cell).

Given N, return the maximal possible score you can get.

 

Definition

    
Class:RoundAboutCircle
Method:maxScore
Parameters:int
Returns:int
Method signature:int maxScore(int N)
(be sure your method is public)
    
 

Constraints

-N will be between 1 and 200000, inclusive.
 

Examples

0)
    
4
Returns: 3
The list of possible moves looks like this:

1->2

2->4

3->2

4->4



You can only visit 3 out of 4 cells, and there are two ways to do so: 1->2->4->4 and 3->2->4->4.
1)
    
5
Returns: 4
If you start on cell 5, the process will terminate after the first move. Otherwise, the token will travel along the loop 1->2->4->3->1 until the entire loop is visited, thus making your score equal to 4.
2)
    
17
Returns: 11
The longest path of the token is 5->10->11->13->17->8->16->6->12->15->4->8.
3)
    
566
Returns: 176

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11126&pm=8705

Writer:

darnley

Testers:

PabloGilberto , Olexiy , ivan_metelsky , ged

Problem categories:

Graph Theory, Simple Search, Iteration