Найдите победителя игры, в которой на каждом ходу выполняется деление N или вычитание.
Джон и Арья играют в игру. Правила игры следующие:
- Изначально они имеют одно число N.
- Оба будут играть альтернативный ход. Джон начинает первым.
- Оба будут играть каждый ход оптимально.
- В каждом ходе они могут выполнять только одну из этих операций:
- Разделите это число на 2, 3, 4 или 5 и возьмите за основу результат.
- Вычтите это число на 2, 3, 4 или 5.
- Если после совершения хода число становится равным 1, игрок, сделавший ход, автоматически проигрывает.
- Когда число становится равным нулю, игра останавливается, а игрок, не сделавший ход, проигрывает.
Найдите победителя игры.
Примеры:
Input: N = 3
Output: Jon
Explanation: Jon will just subtract 3 from initial
number and win the game.Input: N = 6
Output: Arya
Explanation: If Jon subtracts any number or divides N, on the next move Arya can subtract any number and make N as 0.
Подход : проблему можно решить с помощью динамического программирования, основанного на следующей идее:
As Jon is starting the game, he will try to maximize his chances of winning. So, for any value of i, check if there is any possible value less than i (say j) that ensures Jon’s win, i.e., if j was the initial then the one who starts the game would lose. Then on the first move Jon can move from N to j and ensure his win.
Выполните следующие шаги, чтобы решить эту проблему:
- Если N = 1, вернуть «Арья».
- Если N ≤ 5, вернуть «Джон».
- Создайте массив dp[] размером N + 1
- Установите arr[0] = 0 и i = 1.
- Превратите arr[i] в min(arr[5], arr[N]) в 1.
- Установите я = 6.
- Пока i ≤ N, чей бы сейчас ни был ход, проверьте, есть ли какой-нибудь ход, выполнив который он может выиграть, а значит, если любое arr[условие] = 0, то он точно выиграет, иначе нет.
- Если arr[i/2], arr[i/4], arr[i/3] или arr[i/5] равно 0,
- Установить, обр[i] = 1.
- Иначе Если arr[i – 2], arr[i – 3], arr[i – 4] или arr[i – 5] равно 0,
- Установить, обр[i] = 1.
- Еще,
- Установить, обр[i] = 0.
- Увеличивайте i на 1 после каждой итерации.
- Если arr[i/2], arr[i/4], arr[i/3] или arr[i/5] равно 0,
- Если arr[N] = 1, то вернуть «Джон».
- В противном случае верните «Арья».
Ниже приведена реализация описанного выше подхода.
Временная сложность : O(N)
Вспомогательное пространство : O(N)
Статьи по Теме:
- Введение в динамическое программирование — учебные пособия по структурам данных и алгоритмам
- Что такое мемоизация? Полное руководство