ChooseTheBestOne
SRM 619 · 2013-12-22 · by hyy5159
Problem Statement
Shiny wants to give an award to one of the employees in her company. However, all her employees are doing perfect work, so it's hard to pick the one that gets the award. Therefore Shiny organized a game they will play to determine the winner.
At the beginning of the game, all N employees form a circle. Then, they receive t-shirts with numbers 1 through N in clockwise order along the circle. These numbers are never used in the game, we will just use them to identify the winner.
The game is played in turns. The turns are numbered starting from 1. In each turn, Shiny starts by standing in front of some employee (as specified below) and saying "one". Then she moves clockwise along the circle to the next employee and says "two". And so on, until the number she says reaches the threshold for that particular turn. The threshold for turn number t is t^3. (That is, the threshold is 1 for turn 1, 8 for turn 2, 27 for turn 3, and so on.)
At the end of each turn, the employee currently standing in front of Shiny (i.e., the one that received the number t^3) is eliminated. In the very first round Shiny starts in front of the employee with the number 1 on their t-shirt. In each of the following rounds, Shiny starts in front of the next employee clockwise from the one who just got eliminated.
When there is only one employee left in the game, the game ends and the employee wins the award.
You are given the
Constraints
- N will between 1 and 5000, inclusive.
3 Returns: 2
In the first round, Shiny stands in front of employee 1, says "one" and eliminates him. In the second round, Shiny starts in front of employee 2. She says "one" to employee 2, "two" to employee 3, "three" to employee 2 again, ..., and "eight" to employee 3. Thus, employee 3 gets eliminated and employee 2 wins the award.
6 Returns: 6
10 Returns: 8
1234 Returns: 341
2414 Returns: 1368
Submissions are judged against all 92 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ChooseTheBestOne with a public method int countNumber(int N) · 92 test cases · 2 s / 256 MB per case