TopCoder problem "LastStone" used in TCO06 Round 3 (Division I Level One)



Problem Statement

    

Bob and Sally play the following game. At the beginning of the game several stones lie in a box. The two players take stones in turns, and the player who takes the last stone wins. On each turn, a player may take T stones for any T in turns. For each number k between m and n, inclusive, the game is played once with the box containing k stones at the start of the game. Assuming both players play optimally, return how many times Bob will win (Bob always moves first).

 

Definition

    
Class:LastStone
Method:numWins
Parameters:int[], int, int
Returns:int
Method signature:int numWins(int[] turns, int m, int n)
(be sure your method is public)
    
 

Constraints

-turns will contain between 1 and 50 elements, inclusive.
-Each element of turns will be between 1 and 100, inclusive.
-Elements of turns will be in strictly ascending order.
-The first element of turns will be 1.
-n will be between 1 and 100000, inclusive.
-m will be between 1 and n, inclusive.
 

Examples

0)
    
{1, 3, 4}
1
5
Returns: 4
If the box contains 1, 3 or 4 stones, Bob wins by taking them all on his first turn. If the box contains 2 stones, Bob is forced to take 1 stone, and Sally wins by taking the other one. If the box contains 5 stones, Bob takes 3 stones (leaving 2 stones in the box) and wins the game on his next turn.
1)
    
{1}
1
100
Returns: 50
2)
    
{1,2,3,4,5,6,7,8,9,10}
1
10
Returns: 10
3)
    
{1, 2, 3}
1
8
Returns: 6

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9922&pm=6127

Writer:

Olexiy

Testers:

PabloGilberto , lbackstrom , brett1479 , radeye

Problem categories:

Dynamic Programming