Найдите победителя игры, в которой на каждом ходу выполняется деление 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[N] = 1, то вернуть «Джон».
• В противном случае верните «Арья».

Ниже приведена реализация описанного выше подхода.

Временная сложность : O(N)
Вспомогательное пространство : O(N)

Статьи по Теме:

• Введение в динамическое программирование — учебные пособия по структурам данных и алгоритмам
• Что такое мемоизация? Полное руководство