RoundAboutCircle
SRM 392 · 2008-03-06 · by darnley
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.
Constraints
- N will be between 1 and 200000, inclusive.
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
1 Returns: 1
Submissions are judged against all 65 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RoundAboutCircle with a public method int maxScore(int N) · 65 test cases · 2 s / 256 MB per case