TopCoder problem "CountGame" used in SRM 183 (Division II Level One)



Problem Statement

    The Counting Game is a game played between two players. The first player starts counting at 1, and can say no more than maxAdd numbers. The second player continues counting from where the first player left off. The two players alternate, each one contributing at least one but no more than maxAdd numbers. The player who says the goal number is the winner.

For example, if maxAdd is 3 and the goal is 20, then a game (between bad players A and B) might go like this:

A: 1,2,3 ... B: 4,5 ... A: 6 ... B: 7,8,9 ... A: 10,11,12 ... B: 13 ... A: 14 ... B: 15,16 ... A: 17,18 ... B: 19,20

Since player B said the goal number, she was the winner.

There is a perfect strategy for this game. When maxAdd is 3, if you end your turn by saying 16, then no matter whether your opponent contributes 1, 2, or 3 numbers you will be able to count to 20 on your next turn. Similarly, if you end your turn by saying 12, then no matter what your opponent does you can end your next turn by saying 16, and thus win on your following turn.

Create a class CountGame to help you play this game. It should contain a method howMany that is given maxAdd, the most numbers you may say on each turn, goal, the goal number, and next, the number that you must start counting on. The method should return how many numbers you should say. If there is no way for you to force a win, then the method should return -1.

 

Definition

    
Class:CountGame
Method:howMany
Parameters:int, int, int
Returns:int
Method signature:int howMany(int maxAdd, int goal, int next)
(be sure your method is public)
    
 

Notes

-If there is a play that forces a win, it is unique.
 

Constraints

-maxAdd will be between 2 and 8 inclusive.
-goal will be between 1 and 1000 inclusive.
-next will be between 1 and goal inclusive.
 

Examples

0)
    
3
20
10
Returns: 3
This is the game where each player can contribute 1, 2 or 3 numbers and the goal is 20. It is your turn and you must start at 10 (presumably because your opponent ended his previous turn at 9). You should count 10,11,12 since, as shown above, when maxAdd is 3 you can force a win if you end your turn by saying 12.
1)
    
5
20
10
Returns: 5
Count 10,11,12,13,14. Then whatever your opponent does, you will be able to win by counting to 20 on your next turn. Even if he says just 15, you can reach 20 since maxAdd is 5.
2)
    
5
20
9
Returns: -1
Whatever you do, your opponent will be able to end his next turn by saying 14. Then you won't be able to count up to 20, but even if you say just one number, your opponent will be able to win on his turn.
3)
    
4
50
50
Returns: 1
Here the next number is the goal, so we just add that one number to the sequence and win.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4735&pm=2337

Writer:

dgoodman

Testers:

lbackstrom , brett1479

Problem categories:

Simple Math, Simulation