TheNumberGame
SRM 574 · 2012-12-13 · by gojira_tc
Problem Statement
Initially, Manao has an integer A and his friend has an integer B. Note that neither A nor B contain a zero digit in their base 10 representation. The players make moves alternatively with Manao starting first. In each move, the player can either reverse his current number, or he can divide it by 10 (using integer division). For example, if the current number is 12849, the player can either reverse it to obtain 94821, or he can divide it by 10 to obtain 1284. Note that we always round down when using integer division. Also note that each player is only allowed to change his own number, and not the number of the other player.
If after some move the players' numbers become equal, Manao is declared the winner. If after 1000 moves (that is, 500 moves by Manao and 500 by his friend) Manao has not won, he loses. Given A and B, determine whether Manao would win if both players play optimally. Return "Manao wins" or "Manao loses" accordingly.
Constraints
- A will be between 1 and 999,999,999, inclusive.
- B will be between 1 and 999,999,999, inclusive.
- A and B will not contain a zero digit in base 10 representation.
- A and B will be distinct.
45 4 Returns: "Manao wins"
Manao can win in one move by dividing his number by 10.
45 5 Returns: "Manao wins"
There are several possible scenarios this game can follow: Manao divides by 10 and obtains 4. Now his opponent can reverse his number and obtain 5 again. Obviously, no matter what Manao does in his next 499 moves, his opponent can evade him. Manao reverses his number and obtains 54. His opponent reverses his 5. Manao divides 54 by 10 and obtains 5, thus making the numbers equal Manao reverses his number and obtains 54. His opponent divides by 10 and obtains zero. Manao will win in three moves, dividing his number by 10 twice. Obviously, Manao will not choose to divide by 10 in his first move and will win.
99 123 Returns: "Manao loses"
No matter how Manao plays, the opponent can perform reverse moves until the end of the game.
2356236 5666 Returns: "Manao loses"
11 1 Returns: "Manao wins"
Submissions are judged against all 127 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheNumberGame with a public method string determineOutcome(int A, int B) · 127 test cases · 2 s / 256 MB per case