Найдите победителя игры, в которой на каждом ходу выполняется деление N или вычитание.

Опубликовано: 20 Февраля, 2023

Джон и Арья играют в игру. Правила игры следующие:

  • Изначально они имеют одно число 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)

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

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