RoundAboutCircle | Topcoder Archive

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

```
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.
```
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.
```
17
```
```
Returns: 11
```
The longest path of the token is 5->10->11->13->17->8->16->6->12->15->4->8.
```
566
```
```
Returns: 176
```

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)2024, Topcoder, Inc. All rights reserved.