Whoever must play, cannot play def subtract_square(queries): Two players play a game of "Subtract a square", starting with a positive integer. On their turn to play, each player must subtract some square number (1, 4, 9, 16, 25, 36, 49, ...) from the current number so that the result does not become negative. Under the normal play convention of these games, the player who moves to zero wins, leaving his opponent stuck with no possible moves. (In the misère version of the game that has otherwise identical rules but where you win by losing the original game, these definitions would be adjusted accordingly.)
Whoever must play, cannot play
def subtract_square(queries):
Two players play a game of "Subtract a square", starting with a positive integer. On their turn to play, each player must subtract some square number (1, 4, 9, 16, 25, 36, 49, ...) from the current number
so that the result does not become negative. Under the normal play convention of these games, the player who moves to zero wins, leaving his opponent stuck with no possible moves. (In the misère version of the game that has otherwise identical rules but where you win by losing the original game, these definitions would be adjusted accordingly.)
This and many similar combinatorial games can be modelled with recursive equations. This game is an example of an impartial game since the moves available to both players are exactly the same, as
opposed to “partisan games” such as chess where each player can only move pieces of one colour. A game state is therefore determined by the remaining number alone, but not by which player has to make the next move. A state is called hot (“winning”) if it allows at least one move that is part of the winning line regardless of the opponent's response, under the assumption that the current player will then also continue making the best moves until the opponent says uncle. The game state is cold
(“losing”) if no winning move exists in that state.
Since the possible states of this game are the nonnegative integers, the base case for the recursion is that zero is cold. The state n is hot if there exists at least one move m so that n-m*m is cold, otherwise n is cold. Since the heat of each state n depends on heats of states lower than n, we might
as well combine the computations of states into a batch job. Given a list of queries so that each element is a state this function should return a list of results for those queries so that True means hot and False means cold. You should compute the heat values of states as a single list that you
build up from left to right, so that the heat value computation in each state can simply read from this list the already computed heat values of lower-numbered states.
![queries
Expected result
[7, 12, 17, 24]
[False, False, False, True]
[2, 3, 6, 10, 14, 20, 29,
39, 57, 83, 111, 149,
[False, True, True, False, True,
False, True, False, False, True,
220, 304, 455, 681]
True, True, True, True, True, True]
[7, 12, 17, 23, 32, 45,
61, 84, 120, 172, 251,
345, 510, 722, 966, 1301,
1766, 2582, 3523, 5095,
7812, 10784, 14426,
20741]
[False, False, False, True, True,
True, True, True, True, True, True,
False, False, True, True, True,
True, True, True, True, True, True,
True, True]](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F8989f20f-4778-4596-9f56-d6b621379690%2F39e49a51-927e-4bf4-89cb-e9217fc1a732%2Fl3bmgt_processed.png&w=3840&q=75)
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 2 images
