TopCoder problem "TakeSubstringGame" used in SRM 360 (Division II Level Three)



Problem Statement

    

A positive integer n is written on a board, and two players take turns making moves.

In each move, the player selects a positive integer m that is a proper substring of the number currently written on the board. The number on the board is then decreased by m. A proper substring is a substring that doesn't equal the whole string.

For example, if a board contains the number 2309, a player can select m = 2, 3, 9, 23, 30, 230 or 309. Thus the possible moves from 2309 are 2000, 2079, 2279, 2286, 2300, 2306 and 2307.

A player who can't make a valid move loses the game.

Return the number m that the first player should select in his first move in order to win the game. If there are several such numbers, return the smallest among them. If the first player cannot win the game, return -1.

 

Definition

    
Class:TakeSubstringGame
Method:winningMove
Parameters:int
Returns:int
Method signature:int winningMove(int n)
(be sure your method is public)
    
 

Constraints

-n will be between 1 and 1000000, inclusive.
 

Examples

0)
    
5
Returns: -1
A single-digit number doesn't have a proper substring, so there is no valid move for the first player. Thus, the second player wins.
1)
    
10
Returns: 1
Subtracting 0 is not a valid move (m must be positive). So the only valid move is to subtract 1. Now the second player receives number 9 and can't make a move, providing victory for the first player.
2)
    
17
Returns: -1
Subtracting 7 will leave the second player with number 10, which is favorable for him, as shown in example above. Therefore the first player should subtract 1 and leave 16. Similarly, the second player will move on to 15. Three more such pairs of moves and the first player will be facing number 11. He will then subtract 1 and lose as shown above. Thus the second player wins.
3)
    
239
Returns: 9
The optimal first move is to subtract either 9 or 23, leaving 230 or 216. In case of a tie, you should return the smallest subtracted number which is 9.
4)
    
566
Returns: 66
Subtract 66 and leave your opponent with 500, which is apparently a losing position.
5)
    
23900
Returns: -1
No first move is advantageous for the first player.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10772&pm=8026

Writer:

darnley

Testers:

PabloGilberto , Olexiy , lovro , ivan_metelsky

Problem categories:

Dynamic Programming, Simple Math