Я решаю некоторые проблемы из CodeChef, но я застрял на проблеме https://www.codechef.com/MAY19B/problems/MATCHS.I получил эту проблему является проблема динамического программирования. Так что я использовал functools.lru_cache для сохранения результатов функции. Но я получаю ошибку TLE в некоторые тестовые случаи. Как я могу дополнительно оптимизировать код?
Следующая проблема:
Ари и Рич играют в довольно запутанную игру. Вот правила игры:
1. The game is played with two piles of matches. Initially, the first pile
contains N matches and the second one contains M matches.
2. The players alternate turns; Ari plays first.
3. 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.
4. It is only allowed to remove X matches from a pile if the number of
matches in the other pile divides X.
5. The player that takes the last match from any pile wins.
Решить (N, M)
1. Если ход его Ари и N% M == 0, тогда Ари выигрывает, а Рич выигрывает.
2. Если N% M! = 0, то игрок пробует все возможные ходы и проверяет, выиграл ли он один из них.
в итоге.
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