Marble Game
InterviewTime limit1sMemory limit128 MB
Compute Grundy-style win/lose states for a two-pile subtraction game with three fixed move sizes and report the winner for five given starting positions.
- Level
Medium4 of 10
- Topics
- Dynamic programming, Game theory, Math
- Solved
- No attempts yet
Problem
Two players, A and B, play a game with two boxes of marbles. They take turns, with A moving first.
On one turn, a player chooses exactly one of the two boxes and removes one of three specified numbers of marbles from that box. A player cannot remove marbles from both boxes on the same turn.
If a player starts a turn and cannot remove a specified number of marbles from either box, that player loses and the other player wins.
For example, suppose the allowed removal counts are 1, 3, and 4. If the two boxes initially contain 4 and 1 marbles, A wins. If the two boxes initially contain 5 and 5 marbles, B wins.
Given the allowed removal counts b1, b2, b3 and the initial marble counts k1, k2 in the two boxes, determine whether the winner is A or B for each case.
The limits are as follows.
1 <= b1 < b2 < b3 <= 301 <= k1, k2 <= 500
Input
The first line contains three integers b1, b2, and b3, the numbers of marbles that may be removed in one turn.
Each of the next 5 lines contains two integers k1 and k2, the initial numbers of marbles in the two boxes for one case.
Output
For each of the 5 given k1, k2 cases, print one line: A if A wins, or B if B wins, in order.