Найдите игрока, который выиграет, выбрав число в диапазоне [1, K] с общей суммой N

Даны два целых числа K и N , а также известно, что Алиса и Боб играют в игру. За один ход игрок может выбрать число из диапазона [1, K] , и игрок, чье число делает сумму равной N , выигрывает игру. Выведите Alice , если Алиса выигрывает игру, иначе Bob , если Алиса и Боб оба играют в игру альтернативно и оптимально , и Алиса начинает игру.

Примеры:

Input: K = 7, N = 8
Output: Bob
Explanation: There is no way for Alice to win the game. When Alice picks any number from 1 to 7 (inclusive both), the opponent wins the game in the next turn by making the total 8 . Suppose you choose number 5, the opponent chooses 3 and wins the game, making the total 5+3=8 .

Input: K = 7, N = 50
Output: Alice

Подход: Эту проблему можно решить, используя концепцию теории игр. Наблюдение за выигрышным состоянием . Хитрость здесь заключается в том, что Алиса всегда может повторить цикл из (K+1) независимо от выбора Боба. Предположим, что в какой-то момент, если Боб выбирает a , Алиса может выбрать [(K+1)-a ] сохраняя выбор в диапазоне от 1 до K и, таким образом, формируя цикл из (K+1) . Теперь, поскольку у Алисы есть первый шанс, Алиса должна выбрать Остаток, оставшийся при делении N на (K+1) в начале, чтобы после этого она может продолжать повторять цикл (K+1) и получить в сумме N .
Теперь наблюдение состоит в том, что если N%(K+1) равно 0 , это единственный случай, когда невозможно выиграть игру для Алисы.
Следуйте инструкциям ниже, чтобы решить проблему.

• Проверьте, равно ли N%(K+1) 0, распечатайте Bob .
• В любом другом случае Print Alice .

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

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