Задача: игра в ним

Решаем задачи, которые дают программистам на собеседованиях в IT‑компаниях. Сегодня пытаемся понять, можно ли выиграть в ним с заданными условиями.

Иллюстрация: Polina Vari для Skillbox Media

Дмитрий Зверев

Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.

Сергей Голицын

Senior Java Developer в Covalent Inc. и преподаватель. Больше семи лет в Java-разработке. В свободное время судит хакатоны и делится опытом с начинающими программистами. Пишет статьи для «Хабра» и Medium. Ведёт телеграм-каналы «Полезные ссылки около Java» и Cracking code interview.

Условие. Вы играете с оппонентом в ним. Вот правила этой игры:

На старте перед вами лежит кучка камней.
Вы с оппонентом по очереди делаете ходы — причём первый ход всегда за вами.
На каждом ходу игрок убирает из кучи от одного до трёх камней на свой выбор.
Побеждает игрок, который уберёт последний камень.

Дано число камней — n. Вернуть true, если вы сможете выиграть, учитывая, что ваш оппонент будет играть максимально рационально, иначе вернуть false.

Ввод и вывод. Пример 1

Ввод: n = 4
Вывод: false
Пояснение: примерный исход игры:
1. Вы убираете 1 камень. Ваш оппонент убирает 3, включая последний камень. Ваш оппонент побеждает.
2. Вы убираете 2 камня. Ваш оппонент убирает 2 камня, включая последний. Ваш оппонент побеждает.
3. Вы убираете 3 камня. Ваш оппонент убирает последний камень. Ваш оппонент побеждает.

В каждом из вариантов ваш оппонент побеждает.

Пример 2

Ввод: n = 1
Вывод: true

Пример 3

Ввод: n = 2
Вывод: true

Решить эту задачу самостоятельно и на разных языках программирования можно на LeetCode. Наше решение взято из телеграм-канала Сергея Cracking code interview.

Решение

Для начала мы должны понять, какие возможные исходы игровых партий существуют. Уже понятно, что если перед нашим ходом камней всего четыре, то мы проиграем.

Поэтому есть три сценария развития событий:

Камней меньше, чем 4, и сейчас наш ход — мы побеждаем.
Камней ровно 4, и сейчас наш ход — мы точно проиграли.
Камней больше, чем 4, но при этом остаток от деления общего числа камней на 4 равен 0 — значит, мы тоже проиграем, так как по условию наш соперник будет играть честно.

public boolean canWinNim(int n) {
    if (n < 4){
      return true;
    }
    if (n == 4){
      return false;
    }
    if (n % 4 == 0){
      return false;
    }
    return true;
  }