TakeSubstringGame
SRM 360 · 2007-07-24 · by darnley
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.
Constraints
- n will be between 1 and 1000000, inclusive.
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.
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.
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.
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.
566 Returns: 66
Subtract 66 and leave your opponent with 500, which is apparently a losing position.
23900 Returns: -1
No first move is advantageous for the first player.
Submissions are judged against all 96 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TakeSubstringGame with a public method int winningMove(int n) · 96 test cases · 2 s / 256 MB per case