I am solving some problems from CodeChef but I am stuck on the Matches problem:
Ari and Rich are playing a pretty confusing game. Here are the rules of the game:
The game is played with two piles of matches. Initially, the first pile contains N matches and the second one contains M matches.
The players alternate turns; Ari plays first.
On each turn, the current player must choose one pile and remove a positive number of matches (not exceeding the current number of matches on that pile) from it.
It is only allowed to remove X matches from a pile if the number of matches in the other pile divides X.
The player that takes the last match from any pile wins.
- If its Ari's turn and N%M==0 then Ari wins else Rich wins.
- If N%M!=0 then player try every possible moves and check if he wins any one of them in end.
My solution uses Dynamic Programmming, so I have used
functools.lru_cache to save function results. But I am getting TLE error in some test cases.How can I further optimize the code?
from functools import lru_cache @lru_cache(maxsize=None) def Solve(X,Y,Player=True): if X%Y==0: return Player else: temp=X X=X%Y if Player==Solve(max(X,Y),min(X,Y),not Player): return Player while temp!=X+Y: X=X+Y if Player==Solve(max(X,Y),min(X,Y),not Player): return Player return not Player