Задания 19-21

Пример 1

Задача

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза.

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней. В начальный момент в первой куче было семь камней, во второй куче – S камней; 1 ≤ S ≤ 69.

Задание 19

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

В этой задаче неудачный ход Пети - это просто ход, который привёл к выигрышу Васи за один ход.

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

Если совсем упрощать, то нам надо перебрать все варианты первых ходов Вани и Пети, и сели хоть одна пара ходов приведёт к победе Вани, значит, это значение S нам подходит.

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

Ход выполняется во время вызова метода хода соперника за счёт того, что мы меняем значения в аргументах.

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

Java
C++
Python

public class Example1 {

    // ход Пети, результат отвечает на вопрос, удовлетворяется ли
    // требование задачи,  l - кол-во камней в первой куче, r - во второй,
    // step - номер хода
    static boolean player1(int l, int r, int step) {
        // если это первый ход Пети, тогда Ваня пока что
        // не сделал ни одного хода
        if (step == 1) {
            // перебираем разные ходы Пети, нас устроит если хотя бы один
            // приведёт к выигрышу, поэтому используем ИЛИ
            // часть этих ходов может оказаться неудачной,
            // обработка этих ходов вернёт true
            // и в итоге приведёт к победе Вани
            return player2(l + 1, r, step) ||
                    player2(l, r + 1, step) ||
                    player2(l * 2, r, step) ||
                    player2(l, r * 2, step);
        } else { // если это второй ход Пети, Ваня ужк сделал первый ход
            // если сумма больше 77, то Ваня победил, условие
            // задачи выполнено
            return l + r >= 77;
        }

    }

    // ход Вани, результат отвечает на вопрос, удовлетворяется ли
    // требование задачи второго хода Вани не предполагается, поэтому
    // этот метод вызовется только для первого хода,
    // l - кол-во камней в первой куче, r - во второй,  step - номер хода
    static boolean player2(int l, int r, int step) {
        // перебираем разные ходы Вани, нас устроит если хотя бы один
        // приведёт к выигрышу, поэтому используем ИЛИ
        return player1(l + 1, r, step + 1) ||
                player1(l, r + 1, step + 1) ||
                player1(l * 2, r, step + 1) ||
                player1(l, r * 2, step + 1);
    }


    public static void main(String[] args) {
        // перебираем кол-во камней во второй куче
        for (int s = 1; s < 69; s++) {
            // запускаем обработку первого шага Пети, если
            // нас устраивает результат,
            if (player1(7, s, 1)) {
                // выводим кол-во камней во второй куче
                System.out.println(s);
                // завершаем цикл
                break;
            }
        }
    }
}

#include <iostream>

// декларируем метод хода второго игрока
bool player2(int l, int r, int step);

// ход Пети, результат отвечает на вопрос, удовлетворяется ли
// требование задачи,  l - кол-во камней в первой куче, r - во второй,
// step - номер хода
bool player1(int l, int r, int step) {
    // если это первый ход Пети, тогда Ваня пока что
    // не сделал ни одного хода
    if (step == 1) {
        // перебираем разные ходы Пети, нас устроит если хотя бы один
        // приведёт к выигрышу, поэтому используем ИЛИ
        // часть этих ходов может оказаться неудачной,
        // обработка этих ходов вернёт true
        // и в итоге приведёт к победе Вани
        return player2(l + 1, r, step) ||
               player2(l, r + 1, step) ||
               player2(l * 2, r, step) ||
               player2(l, r * 2, step);
    } else { // если это второй ход Пети, Ваня ужк сделал первый ход
        // если сумма больше 77, то Ваня победил, условие
        // задачи выполнено
        return l + r >= 77;
    }

}

// ход Вани, результат отвечает на вопрос, удовлетворяется ли
// требование задачи второго хода Вани не предполагается, поэтому
// этот метод вызовется только для первого хода,
// l - кол-во камней в первой куче, r - во второй,  step - номер хода
bool player2(int l, int r, int step) {
    // перебираем разные ходы Вани, нас устроит если хотя бы один
    // приведёт к выигрышу, поэтому используем ИЛИ
    return player1(l + 1, r, step + 1) ||
           player1(l, r + 1, step + 1) ||
           player1(l * 2, r, step + 1) ||
           player1(l, r * 2, step + 1);
}

// главный метод программы
int main() {
    // перебираем кол-во камней во второй куче
    for (int s = 1; s < 69; s++) {
        // запускаем обработку первого шага Пети, если
        // нас устраивает результат,
        if (player1(7, s, 1)) {
            // выводим кол-во камней во второй куче
            std::cout << s << std::endl;
            // завершаем цикл
            break;
        }
    }
    return 0;
}

# ход Пети, результат отвечает на вопрос, удовлетворяется ли
# требование задачи,  l - кол-во камней в первой куче, r - во второй,
# step - номер хода
def player1(l, r, step):
    # если это первый ход Пети, тогда Ваня пока что
    # не сделал ни одного хода
    if step == 1:
        # перебираем разные ходы Пети, нас устроит если хотя бы один
        # приведёт к выигрышу, поэтому используем ИЛИ
        # часть этих ходов может оказаться неудачной,
        # обработка этих ходов вернёт true
        # и в итоге приведёт к победе Вани
        return player2(l + 1, r, step) or player2(l, r + 1, step) \
               or player2(l * 2, r, step) or player2(l, r * 2, step)
    # если это второй ход Пети, Ваня ужк сделал первый ход
    else:
        # если сумма больше 77, то Ваня победил, условие
        # задачи выполнено
        return l + r >= 77


# ход Вани, результат отвечает на вопрос, удовлетворяется ли
# требование задачи второго хода Вани не предполагается, поэтому
# этот метод вызовется только для первого хода,
# l - кол-во камней в первой куче, r - во второй,  step - номер хода
def player2(l, r, step):
    # перебираем разные ходы Вани, нас устроит если хотя бы один
    # приведёт к выигрышу, поэтому используем ИЛИ
    return player1(l + 1, r, step + 1) or player1(l, r + 1, step + 1) \
           or player1(l * 2, r, step + 1) or player1(l, r * 2, step + 1)


# перебираем кол-во камней во второй куче
for s in range(1, 69 + 1):
    # запускаем обработку первого шага Пети, если
    # нас устраивает результат,
    if player1(7, s, 1):
        # выводим кол-во камней во второй куче
        print(s)
        # завершаем цикл
        break
        

Вывод программы:

Ответ: 18

Задание 20

Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

Петя не может выиграть за один ход;
Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

Эта задача решается схожим образом. Когда говорится, что есть выигрышная стратегия, это значит, что на любой ход Вани у Пети есть второй выигрышный ход.

Java
C++
Python

public class Example2 {

    // ход Пети, результат отвечает на вопрос, удовлетворяется ли
    // требование задачи,
    // l - кол-во камней в первой куче, r - во второй, step - номер хода
    static boolean player1(int l, int r, int step) {
        // если это первый ход Пети, тогда Ваня пока что
        // не сделал ни одного хода
        if (step == 1) {
            // выигрышная стратегия подразумевает, что
            // при любом поведении Вани требование задачи должно быть удовлетворено,
            // если говорится, что стратегия есть, значит,
            // нам подойдёт, если условие задачи выполнится в случае
            // хотя бы одного хода, поэтому используем ИЛИ
            return player2(l + 1, r, step) ||
                    player2(l, r + 1, step) ||
                    player2(l * 2, r, step) ||
                    player2(l, r * 2, step);
        } else { // если это второй ход Пети, т.е. Ваня сделал уже один ход
            // если Ваня при этом победил,
            if (l + r >= 77)
                // требование задачи не выполнено
                return false;

            // каким-то своим ходом Петя может выиграть,
            // то условие задачи будет выполнено, поэтому ИЛИ
            return player2(l + 1, r, step) ||
                    player2(l, r + 1, step) ||
                    player2(l * 2, r, step) ||
                    player2(l, r * 2, step);
        }
    }

    // ход Вани, результат отвечает на вопрос, удовлетворяется ли
    // требование задачи,
    // l - кол-во камней в первой куче, r - во второй,  step - номер хода
    static boolean player2(int l, int r, int step) {
        // обработка состояния игры после хода Пети
        // если Петя сделал первый ход
        if (step == 1) {
            // если он при этом победил,
            if (l + r >= 77)
                // требование задачи не выполнено
                return false;

            // разные ходы Вани
            // нам нужно, чтобы при любом ходе Вани Петя победил, т.е.
            // требование задачи было выполнено, поэтому используем И
            return player1(l + 1, r, step + 1) &&
                    player1(l, r + 1, step + 1) &&
                    player1(l * 2, r, step + 1) &&
                    player1(l, r * 2, step + 1);
        } else { // если Петя сделал второй ход
            // он должен победить
            return l + r >= 77;
        }
    }

    // проверка, может ли Петя выиграть первым ходом
    public static boolean check(int l, int r) {
        return l + 1 + r >= 77 || l + r + 1 >= 77 || l * 2 + r >= 77 || l + r * 2 >= 77;
    }

    public static void main(String[] args) {
        // перебираем кол-во камней во второй куче
        for (int s = 0; s < 69; s++) {
            // запускаем обработку первого шага Пети, если
            // Петя не может выиграть за один ход и
            // Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня
            if (!check(7, s) && player1(7, s, 1)) {
                // выводим кол-во камней во второй куче
                System.out.println(s);
            }
        }
    }
}

#include <iostream>


// декларируем метод хода второго игрока
bool player2(int l, int r, int step);

// ход Пети, результат отвечает на вопрос, удовлетворяется ли
// требование задачи,
// l - кол-во камней в первой куче, r - во второй, step - номер хода
bool player1(int l, int r, int step) {
    // если это первый ход Пети, тогда Ваня пока что
    // не сделал ни одного хода
    if (step == 1) {
        // выигрышная стратегия подразумевает, что
        // при любом поведении Вани требование  задачи должно быть удовлетворено,
        // если говорится, что тсратегия есть, значит,
        // нам подойдёт, если условие задачи выполнится в случае
        // хотя бы одного хода, поэтому используем ИЛИ
        return player2(l + 1, r, step) ||
               player2(l, r + 1, step) ||
               player2(l * 2, r, step) ||
               player2(l, r * 2, step);
    } else { // если это второй ход Пети, т.е. Ваня сделал уже один ход
        // если Ваня при этом победил,
        if (l + r >= 77)
            // требование задачи не выполнено
            return false;

        // каким-то своим ходом Петя может выиграть,
        // то условие задачи будет выполнено, поэтому ИЛИ
        return player2(l + 1, r, step) ||
               player2(l, r + 1, step) ||
               player2(l * 2, r, step) ||
               player2(l, r * 2, step);
    }
}

// ход Вани, результат отвечает на вопрос, удовлетворяется ли
// требование задачи,
// l - кол-во камней в первой куче, r - во второй,  step - номер хода
bool player2(int l, int r, int step) {
    // обработка состояния игры после хода Пети
    // если Петя сделал первый ход
    if (step == 1) {
        // если он при этом победил,
        if (l + r >= 77)
            // требование задачи не выполнено
            return false;

        // разные ходы Вани
        // нам нужно, чтобы при любом ходе Вани Петя победил, т.е.
        // требование задачи было выполнено, поэтому используем И
        return player1(l + 1, r, step + 1) &&
               player1(l, r + 1, step + 1) &&
               player1(l * 2, r, step + 1) &&
               player1(l, r * 2, step + 1);
    } else { // если Петя сделал второй ход
        // он должен победить
        return l + r >= 77;
    }
}


// проверка, может ли Петя выиграть первым ходом
bool check(int l, int r) {
    return l + 1 + r >= 77 || l + r + 1 >= 77 || l * 2 + r >= 77 || l + r * 2 >= 77;
}


// главный метод программы
int main() {
    // перебираем кол-во камней во второй куче
    for (int s = 1; s < 69; s++) {
        // запускаем обработку первого шага Пети, если
        // Петя не может выиграть за один ход и
        // Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня
        if (!check(7, s) && player1(7, s, 1)) {
            // выводим кол-во камней во второй куче
            std::cout << s << std::endl;
        }
    }
    return 0;
}

# ход Пети, результат отвечает на вопрос, удовлетворяется ли
# требование задачи,
# l - кол-во камней в первой куче, r - во второй, step - номер хода
def player1(l, r, step):
    # если это первый ход Пети, тогда Ваня пока что
    # не сделал ни одного хода
    if step == 1:
        # выигрышная стратегия подразумевает, что
        # при любом поведении Вани требование  задачи должно быть удовлетворено,
        # если говорится, что тсратегия есть, значит,
        # нам подойдёт, если условие задачи выполнится в случае
        # хотя бы одного хода, поэтому используем ИЛИ
        return player2(l + 1, r, step) or player2(l, r + 1, step) or \
               player2(l * 2, r, step) or player2(l, r * 2, step)
    # если это второй ход Пети, т.е. Ваня сделал уже один ход
    else:
        # если Ваня при этом победил,
        if l + r >= 77:
            # требование задачи не выполнено
            return False

        # каким-то своим ходом Петя может выиграть,
        # то условие задачи будет выполнено, поэтому ИЛИ
        return player2(l + 1, r, step) or player2(l, r + 1, step) or \
               player2(l * 2, r, step) or player2(l, r * 2, step)


# ход Вани, результат отвечает на вопрос, удовлетворяется ли
# требование задачи,
# l - кол-во камней в первой куче, r - во второй,  step - номер хода
def player2(l, r, step):
    # обработка состояния игры после хода Пети
    # если Петя сделал первый ход
    if step == 1:
        # если он при этом победил,
        if l + r >= 77:
            # требование задачи не выполнено
            return False

        # разные ходы Вани
        # нам нужно, чтобы при любом ходе Вани Петя победил, т.е.
        # требование задачи было выполнено, поэтому используем И
        return player1(l + 1, r, step + 1) and player1(l, r + 1, step + 1) \
               and player1(l * 2, r, step + 1) and player1(l, r * 2, step + 1)
    # если Петя сделал второй ход
    else:
        # он должен победить
        return l + r >= 77


# проверка, может ли Петя выиграть первым ходом
def check(l, r):
    return l + 1 + r >= 77 or l + r + 1 >= 77 or l * 2 + r >= 77 or l + r * 2 >= 77


# перебираем кол-во камней во второй куче
for s in range(1, 69 + 1):
    # запускаем обработку первого шага Пети, если
    # Петя не может выиграть за один ход и
    # Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня
    if not check(7, s) and player1(7, s, 1):
        # выводим кол-во камней во второй куче
        print(s)

Вывод программы:

31
34

Ответ: 31 34

Задание 21

Найдите минимальное значение S, при котором одновременно выполняются два условия:

у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

В этой задаче проще всего разнести проверки требований в разные методы. player1() и player2() - проверяют первое требование задачи, checkPlayer1() и checkPlayer2() - второе.

Java
C++
Python

public class Example3 {


    // ход Пети, результат отвечает на вопрос, выполняется ли первое
    // требование задачи,
    // l - кол-во камней в первой куче, r - во второй,  step - номер хода
    static boolean player1(int l, int r, int step) {
        // если это первый ход Пети, тогда Ваня пока что
        // не сделал ни одного хода
        if (step == 1) {
            // При любом ходе Пети Ваня должен победить,
            // поэтому используем И
            return player2(l + 1, r, step) &&
                    player2(l, r + 1, step) &&
                    player2(l * 2, r, step) &&
                    player2(l, r * 2, step);

        } else if (step == 2) { // если это второй ход Пети, т.е. Ваня сделал уже один ход
            // если Ваня при этом победил,
            if (l + r >= 77)
                // требование задачи выполнено
                return true;

            // При любом ходе Пети Ваня должен победить,
            // поэтому используем И
            return player2(l + 1, r, step) &&
                    player2(l, r + 1, step) &&
                    player2(l * 2, r, step) &&
                    player2(l, r * 2, step);
        } else { // если это третий ход Пети, т.е. Ваня сделал уже два хода
            // если Ваня при этом победил, то требование задачи не выполнено
            return l + r >= 77;
        }
    }

    // ход Вани, результат отвечает на вопрос, выполняется ли первое
    // требование задачи,
    // l - кол-во камней в первой куче, r - во второй,  step - номер хода
    static boolean player2(int l, int r, int step) {
        // обработка состояния игры после хода Пети
        // если Петя сделал первый ход
        if (step == 1) {
            // если он при этом победил,
            if (l + r >= 77)
                // требование задачи не выполнено
                return false;

            // разные ходы Вани
            // у Вани есть стратегия, которая позволит ему гарантированно выиграть первым ходом
            // или вторым ходом, т.е. есть хотя бы один ход, ведущий к победе,
            return player1(l + 1, r, step + 1) ||
                    player1(l, r + 1, step + 1) ||
                    player1(l * 2, r, step + 1) ||
                    player1(l, r * 2, step + 1);
        } else { // если Петя сделал второй ход
            // если он при этом победил,
            if (l + r >= 77)
                // требование задачи не выполнено
                return false;

            // у Вани есть стратегия, которая позволит ему гарантированно выиграть первым ходом
            // или вторым ходом, т.е. есть хотя бы один ход, ведущий к победе,
            return player1(l + 1, r, step + 1) ||
                    player1(l, r + 1, step + 1) ||
                    player1(l * 2, r, step + 1) ||
                    player1(l, r * 2, step + 1);
        }
    }


    // ход Пети, результат отвечает на вопрос, выполняется ли второе
    // требование задачи,
    // l - кол-во камней в первой куче, r - во второй,  step - номер хода
    static boolean checkPlayer1(int l, int r, int step) {
        if (step == 1) {
            // При любом ходе Пети Ваня не должен гарантированно победить,
            // поэтому отрицаем выражение и используем И
            return !(checkPlayer2(l + 1, r, step) &&
                    checkPlayer2(l, r + 1, step) &&
                    checkPlayer2(l * 2, r, step) &&
                    checkPlayer2(l, r * 2, step));
        } else { // если это второй ход Пети, т.е. Ваня сделал уже один ход
            // если он при этом победил, возвращаем, что условие выполнено
            return l + r >= 77;
        }
    }

    // ход Вани, результат отвечает на вопрос, выполняется ли второе
    // требование задачи
    // l - кол-во камней в первой куче, r - во второй,  step - номер хода
    static boolean checkPlayer2(int l, int r, int step) {
        // При любом ходе Пети Ваня должен победить,
        // поэтому используем И
        return checkPlayer1(l + 1, r, step + 1) ||
                checkPlayer1(l, r + 1, step + 1) ||
                checkPlayer1(l * 2, r, step + 1) ||
                checkPlayer1(l, r * 2, step + 1);
    }


    public static void main(String[] args) {
        // перебираем кол-во камней во второй куче
        for (int s = 0; s < 69; s++) {
            // запускаем обработку первого шага Пети, если
            // нас устраивает результат, проверки выполняем отдельными методами
            if (player1(7, s, 1) && checkPlayer1(7, s, 1)) {
                // выводим кол-во камней во второй куче
                System.out.println(s);

                break;
            }
        }
    }
}

#include <iostream>


// декларируем метод хода второго игрока
bool player2(int l, int r, int step);

// декларируем метод хода второго игрока
bool checkPlayer2(int l, int r, int step);


// ход Пети, результат отвечает на вопрос, выполняется ли первое
// требование задачи,
// l - кол-во камней в первой куче, r - во второй,  step - номер хода
bool player1(int l, int r, int step) {
    // если это первый ход Пети, тогда Ваня пока что
    // не сделал ни одного хода
    if (step == 1) {
        // При любом ходе Пети Ваня должен победить,
        // поэтому используем И
        return player2(l + 1, r, step) &&
               player2(l, r + 1, step) &&
               player2(l * 2, r, step) &&
               player2(l, r * 2, step);

    } else if (step == 2) { // если это второй ход Пети, т.е. Ваня сделал уже один ход
        // если Ваня при этом победил,
        if (l + r >= 77)
            // требование задачи выполнено
            return true;

        // При любом ходе Пети Ваня должен победить,
        // поэтому используем И
        return player2(l + 1, r, step) &&
               player2(l, r + 1, step) &&
               player2(l * 2, r, step) &&
               player2(l, r * 2, step);
    } else { // если это третий ход Пети, т.е. Ваня сделал уже два хода
        // если Ваня при этом победил, то требование задачи не выполнено
        return l + r >= 77;
    }
}

// ход Вани, результат отвечает на вопрос, выполняется ли первое
// требование задачи,
// l - кол-во камней в первой куче, r - во второй,  step - номер хода
bool player2(int l, int r, int step) {
    // обработка состояния игры после хода Пети
    // если Петя сделал первый ход
    if (step == 1) {
        // если он при этом победил,
        if (l + r >= 77)
            // требование задачи не выполнено
            return false;

        // разные ходы Вани
        // у Вани есть стратегия, которая позволит ему гарантированно выиграть первым ходом
        // или вторым ходом, т.е. есть хотя бы один ход, ведущий к победе,
        return player1(l + 1, r, step + 1) ||
               player1(l, r + 1, step + 1) ||
               player1(l * 2, r, step + 1) ||
               player1(l, r * 2, step + 1);
    } else { // если Петя сделал второй ход
        // если он при этом победил,
        if (l + r >= 77)
            // требование задачи не выполнено
            return false;

        // у Вани есть стратегия, которая позволит ему гарантированно выиграть первым ходом
        // или вторым ходом, т.е. есть хотя бы один ход, ведущий к победе,
        return player1(l + 1, r, step + 1) ||
               player1(l, r + 1, step + 1) ||
               player1(l * 2, r, step + 1) ||
               player1(l, r * 2, step + 1);
    }
}


// ход Пети, результат отвечает на вопрос, выполняется ли второе
// требование задачи,
// l - кол-во камней в первой куче, r - во второй,  step - номер хода
bool checkPlayer1(int l, int r, int step) {
    if (step == 1) {
        // При любом ходе Пети Ваня не должен гарантированно победить,
        // поэтому отрицаем выражение и используем И
        return !(checkPlayer2(l + 1, r, step) &&
                 checkPlayer2(l, r + 1, step) &&
                 checkPlayer2(l * 2, r, step) &&
                 checkPlayer2(l, r * 2, step));
    } else { // если это второй ход Пети, т.е. Ваня сделал уже один ход
        // если он при этом победил, возвращаем, что условие выполнено
        return l + r >= 77;
    }
}

// ход Вани, результат отвечает на вопрос, выполняется ли второе
// требование задачи
// l - кол-во камней в первой куче, r - во второй,  step - номер хода
bool checkPlayer2(int l, int r, int step) {
    // При любом ходе Пети Ваня должен победить,
    // поэтому используем И
    return checkPlayer1(l + 1, r, step + 1) ||
           checkPlayer1(l, r + 1, step + 1) ||
           checkPlayer1(l * 2, r, step + 1) ||
           checkPlayer1(l, r * 2, step + 1);
}



// главный метод программы
int main() {
    // перебираем кол-во камней во второй куче
    for (int s = 1; s < 69; s++) {
        // запускаем обработку первого шага Пети, если
        // нас устраивает результат,
        if (player1(7, s, 1)) {
            // выводим кол-во камней во второй куче
            std::cout << s << std::endl;
            // завершаем цикл
            break;
        }
    }
    return 0;
}

# ход Пети, результат отвечает на вопрос, выполняется ли первое
# требование задачи,
# l - кол-во камней в первой куче, r - во второй,  step - номер хода
def player1(l, r, step):
    # если это первый ход Пети, тогда Ваня пока что
    # не сделал ни одного хода
    if step == 1:
        # При любом ходе Пети Ваня должен победить,
        # поэтому используем И
        return player2(l + 1, r, step) and player2(l, r + 1, step) \
               and player2(l * 2, r, step) and player2(l, r * 2, step)
    # если это второй ход Пети, т.е. Ваня сделал уже один ход
    elif step == 2:
        # если Ваня при этом победил,
        if l + r >= 77:
            # требование задачи выполнено
            return True

        # При любом ходе Пети Ваня должен победить,
        # поэтому используем И
        return player2(l + 1, r, step) and player2(l, r + 1, step) \
               and player2(l * 2, r, step) and player2(l, r * 2, step)
    # если это третий ход Пети, т.е. Ваня сделал уже два хода
    else:
        # если Ваня при этом победил, то требование задачи не выполнено
        return l + r >= 77


# ход Вани, результат отвечает на вопрос, выполняется ли первое
# требование задачи,
# l - кол-во камней в первой куче, r - во второй,  step - номер хода
def player2(l, r, step):
    # обработка состояния игры после хода Пети
    # если Петя сделал первый ход
    if step == 1:
        # если он при этом победил,
        if l + r >= 77:
            # требование задачи не выполнено
            return False

        # разные ходы Вани
        # у Вани есть стратегия, которая позволит ему гарантированно выиграть первым ходом
        # или вторым ходом, т.е. есть хотя бы один ход, ведущий к победе,
        return player1(l + 1, r, step + 1) or player1(l, r + 1, step + 1) \
               or player1(l * 2, r, step + 1) or player1(l, r * 2, step + 1);
    # если Петя сделал второй ход
    else:
        # если он при этом победил,
        if l + r >= 77:
            # требование задачи не выполнено
            return False

        # у Вани есть стратегия, которая позволит ему гарантированно выиграть первым ходом
        # или вторым ходом, т.е. есть хотя бы один ход, ведущий к победе,
        return player1(l + 1, r, step + 1) or player1(l, r + 1, step + 1) \
               or player1(l * 2, r, step + 1) or player1(l, r * 2, step + 1)


# ход Пети, результат отвечает на вопрос, выполняется ли второе
# требование задачи,
# l - кол-во камней в первой куче, r - во второй,  step - номер хода
def checkPlayer1(l, r, step):
    if step == 1:
        # При любом ходе Пети Ваня не должен гарантированно победить,
        # поэтому отрицаем выражение и используем И
        return not (checkPlayer2(l + 1, r, step) and checkPlayer2(l, r + 1, step) \
                    and checkPlayer2(l * 2, r, step) and checkPlayer2(l, r * 2, step))
        # если это второй ход Пети, т.е. Ваня сделал уже один ход
    else:
        # если он при этом победил, возвращаем, что условие выполнено
        return l + r >= 77

    # ход Вани, результат отвечает на вопрос, выполняется ли второе
    # требование задачи
    # l - кол-во камней в первой куче, r - во второй,  step - номер хода

# ход Вани, результат отвечает на вопрос, выполняется ли второе
# требование задачи
# l - кол-во камней в первой куче, r - во второй,  step - номер хода
def checkPlayer2(l, r, step):
    # При любом ходе Пети Ваня должен победить,
    #  поэтому используем И
    return checkPlayer1(l + 1, r, step + 1) or checkPlayer1(l, r + 1, step + 1) \
           or checkPlayer1(l * 2, r, step + 1) or checkPlayer1(l, r * 2, step + 1)


# перебираем кол-во камней во второй куче
for s in range(1, 69 + 1):
    # запускаем обработку первого шага Пети, если
    # нас устраивает результат,
    if player1(7, s, 1) and checkPlayer1(7, s, 1):
        # выводим кол-во камней во второй куче
        print(s)
        # завершаем цикл
        break

Вывод программы:

Ответ: 30

Пример 2

Задача

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить в кучу четыре камня, или увеличить количество камней в куче в 2 раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 19 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 52. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 52 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 51.

Этот блок задач решается практически также, нужно только поменять две кучи на одну.

Задание 19

Java
C++
Python

public class Example4 {

    // ход Пети, результат отвечает на вопрос, удовлетворяется ли
    // требование задачи, s - кол-во камней в куче, step - номер хода
    static boolean player1(int s, int step) {
        // если это первый ход Пети, тогда Ваня пока что
        // не сделал ни одного хода
        if (step == 1) {
            // перебираем разные ходы Пети, нас устроит если хотя бы один
            // приведёт к выигрышу, поэтому используем ИЛИ
            // часть этих ходов может оказаться неудачной,
            // обработка этих ходов вернёт true
            // и в итоге приведёт к победе Вани
            return player2(s + 1, step) ||
                    player2(s + 4, step) ||
                    player2(s * 2, step);
        } else { // если это второй ход Пети, Ваня ужк сделал первый ход
            // если сумма больше 77, то Ваня победил, условие
            // задачи выполнено
            return s >= 52;
        }

    }

    // ход Вани, результат отвечает на вопрос, удовлетворяется ли
    // требование задачи второго хода Вани не предполагается, поэтому
    // этот метод вызовется только для первого хода,
    // s - кол-во камней в куче, step - номер хода
    static boolean player2(int s, int step) {
        // перебираем разные ходы Вани, нас устроит если хотя бы один
        // приведёт к выигрышу, поэтому используем ИЛИ
        return player1(s + 1, step + 1) ||
                player1(s + 4, step + 1) ||
                player1(s * 2, step + 1);
    }


    public static void main(String[] args) {
        // перебираем кол-во камней в куче
        for (int s = 1; s < 51; s++) {
            // запускаем обработку первого шага Пети, если
            // нас устраивает результат,
            if (player1(s, 1)) {
                // выводим кол-во камней во второй куче
                System.out.println(s);
                // завершаем цикл
                break;
            }
        }
    }
}

#include <iostream>

// декларируем метод хода второго игрока
bool player2(int s, int step);

// ход Пети, результат отвечает на вопрос, удовлетворяется ли
// требование задачи, s - кол-во камней в куче, step - номер хода
bool player1(int s, int step) {
    // если это первый ход Пети, тогда Ваня пока что
    // не сделал ни одного хода
    if (step == 1) {
        // перебираем разные ходы Пети, нас устроит если хотя бы один
        // приведёт к выигрышу, поэтому используем ИЛИ
        // часть этих ходов может оказаться неудачной,
        // обработка этих ходов вернёт true
        // и в итоге приведёт к победе Вани
        return player2(s + 1, step) ||
               player2(s + 4, step) ||
               player2(s * 2, step);
    } else { // если это второй ход Пети, Ваня ужк сделал первый ход
        // если сумма больше 77, то Ваня победил, условие
        // задачи выполнено
        return s >= 52;
    }

}

// ход Вани, результат отвечает на вопрос, удовлетворяется ли
// требование задачи второго хода Вани не предполагается, поэтому
// этот метод вызовется только для первого хода,
// s - кол-во камней в куче, step - номер хода
bool player2(int s, int step) {
    // перебираем разные ходы Вани, нас устроит если хотя бы один
    // приведёт к выигрышу, поэтому используем ИЛИ
    return player1(s + 1, step + 1) ||
           player1(s + 4, step + 1) ||
           player1(s * 2, step + 1);
}

// главный метод программы
int main() {
    // перебираем кол-во камней в куче
    for (int s = 1; s < 51; s++) {
        // запускаем обработку первого шага Пети, если
        // нас устраивает результат,
        if (player1(s, 1)) {
            // выводим кол-во камней во второй куче
            std::cout << s << std::endl;
            // завершаем цикл
            break;
        }
    }
    return 0;
}

# ход Пети, результат отвечает на вопрос, удовлетворяется ли
# требование задачи, s - кол-во камней в куче, step - номер хода
def player1(s, step):
    # если это первый ход Пети, тогда Ваня пока что
    # не сделал ни одного хода
    if step == 1:
        # перебираем разные ходы Пети, нас устроит если хотя бы один
        # приведёт к выигрышу, поэтому используем ИЛИ
        # часть этих ходов может оказаться неудачной,
        # обработка этих ходов вернёт true
        # и в итоге приведёт к победе Вани
        return player2(s + 1, step) or player2(s + 4, step) or player2(s * 2, step)
    # если это второй ход Пети, Ваня ужк сделал первый ход
    else:
        # если сумма больше 77, то Ваня победил, условие
        # задачи выполнено
        return s >= 52


# ход Вани, результат отвечает на вопрос, удовлетворяется ли
# требование задачи второго хода Вани не предполагается, поэтому
# этот метод вызовется только для первого хода,
# s - кол-во камней в куче, step - номер хода
def player2(s, step):
    # перебираем разные ходы Вани, нас устроит если хотя бы один
    # приведёт к выигрышу, поэтому используем ИЛИ
    return player1(s + 1, step + 1) or player1(s + 4, step + 1) or player1(s * 2, step + 1)


# перебираем кол-во камней в куче
for s in range(1, 51 + 1):
    # запускаем обработку первого шага Пети, если
    # нас устраивает результат,
    if player1(s, 1):
        # выводим кол-во камней во второй куче
        print(s)
        # завершаем цикл
        break

Вывод программы:

Ответ: 13

Задание 20

Петя не может выиграть за один ход;
Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

Java
C++
Python

public class Example5 {

    // ход Пети, результат отвечает на вопрос, удовлетворяется ли
    // требование задачи,
    // s - кол-во камней в куче, step - номер хода
    static boolean player1(int s, int step) {
        // если это первый ход Пети, тогда Ваня пока что
        // не сделал ни одного хода
        if (step == 1) {
            // выигрышная стратегия подразумевает, что
            // при любом поведении Вани требование  задачи должно быть удовлетворено,
            // если говорится, что тсратегия есть, значит,
            // нам подойдёт, если условие задачи выполнится в случае
            // хотя бы одного хода, поэтому используем ИЛИ
            return player2(s + 1, step) ||
                    player2(s + 4, step) ||
                    player2(s * 2, step);
        } else { // если это второй ход Пети, т.е. Ваня сделал уже один ход
            // если Ваня при этом победил,
            if (s >= 52)
                // требование задачи не выполнено
                return false;

            // каким-то своим ходом Петя может выиграть,
            // то условие задачи будет выполнено, поэтому ИЛИ
            return player2(s + 1, step) ||
                    player2(s + 4, step) ||
                    player2(s * 2, step);
        }
    }

    // ход Вани, результат отвечает на вопрос, удовлетворяется ли
    // требование задачи,
    // s - кол-во камней в куче, step - номер хода
    static boolean player2(int s, int step) {
        // обработка состояния игры после хода Пети
        // если Петя сделал первый ход
        if (step == 1) {
            // если он при этом победил,
            if (s >= 52)
                // требование задачи не выполнено
                return false;

            // разные ходы Вани
            // нам нужно, чтобы при любом ходе Вани Петя победил, т.е.
            // требование задачи было выполнено, поэтому используем И
            return player1(s + 1, step + 1) &&
                    player1(s + 4, step + 1) &&
                    player1(s * 2, step + 1);
        } else { // если Петя сделал второй ход
            // он должен победить
            return s >= 52;
        }
    }

    // проверка, может ли Петя выиграть первым ходом
    public static boolean check(int s) {
        return s + 1 >= 52 || s + 4 >= 52 || s * 2 >= 52;
    }


    public static void main(String[] args) {
        // перебираем кол-во камней в куче
        for (int s = 0; s < 51; s++) {
            // запускаем обработку первого шага Пети, если
            // Петя не может выиграть за один ход и
            // Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня
            if (!check(s) && player1(s, 1)) {
                // выводим кол-во камней во второй куче
                System.out.println(s);
            }
        }
    }
}

#include <iostream>


// декларируем метод хода второго игрока
bool player2(int s, int step);

// ход Пети, результат отвечает на вопрос, удовлетворяется ли
// требование задачи,
// s - кол-во камней в куче, step - номер хода
bool player1(int s, int step) {
    // если это первый ход Пети, тогда Ваня пока что
    // не сделал ни одного хода
    if (step == 1) {
        // выигрышная стратегия подразумевает, что
        // при любом поведении Вани требование  задачи должно быть удовлетворено,
        // если говорится, что тсратегия есть, значит,
        // нам подойдёт, если условие задачи выполнится в случае
        // хотя бы одного хода, поэтому используем ИЛИ
        return player2(s + 1, step) ||
               player2(s + 4, step) ||
               player2(s * 2, step);
    } else { // если это второй ход Пети, т.е. Ваня сделал уже один ход
        // если Ваня при этом победил,
        if (s >= 52)
            // требование задачи не выполнено
            return false;

        // каким-то своим ходом Петя может выиграть,
        // то условие задачи будет выполнено, поэтому ИЛИ
        return player2(s + 1, step) ||
               player2(s + 4, step) ||
               player2(s * 2, step);
    }
}

// ход Вани, результат отвечает на вопрос, удовлетворяется ли
// требование задачи,
// s - кол-во камней в куче, step - номер хода
bool player2(int s, int step) {
    // обработка состояния игры после хода Пети
    // если Петя сделал первый ход
    if (step == 1) {
        // если он при этом победил,
        if (s >= 52)
            // требование задачи не выполнено
            return false;

        // разные ходы Вани
        // нам нужно, чтобы при любом ходе Вани Петя победил, т.е.
        // требование задачи было выполнено, поэтому используем И
        return player1(s + 1, step + 1) &&
               player1(s + 4, step + 1) &&
               player1(s * 2, step + 1);
    } else { // если Петя сделал второй ход
        // он должен победить
        return s >= 52;
    }
}

// проверка, может ли Петя выиграть первым ходом
bool check(int s) {
    return s + 1 >= 52 || s + 4 >= 52 || s * 2 >= 52;
}


// главный метод программы
int main() {
    // перебираем кол-во камней в куче
    for (int s = 1; s < 51; s++) {
        // запускаем обработку первого шага Пети, если
        // Петя не может выиграть за один ход и
        // Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня
        if (!check(s) && player1(s, 1)) {
            // выводим кол-во камней во второй куче
            std::cout << s << std::endl;
        }
    }
    return 0;
}

# ход Пети, результат отвечает на вопрос, удовлетворяется ли
# требование задачи,
# s - кол-во камней в куче, step - номер хода
def player1(s, step):
    # если это первый ход Пети, тогда Ваня пока что
    # не сделал ни одного хода
    if step == 1:
        # выигрышная стратегия подразумевает, что
        # при любом поведении Вани требование  задачи должно быть удовлетворено,
        # если говорится, что тсратегия есть, значит,
        # нам подойдёт, если условие задачи выполнится в случае
        # хотя бы одного хода, поэтому используем ИЛИ
        return player2(s + 1, step) or player2(s + 4, step) or player2(s * 2, step)
    # если это второй ход Пети, т.е. Ваня сделал уже один ход
    else:
        # если Ваня при этом победил,
        if s >= 52:
            # требование задачи не выполнено
            return False

        # каким-то своим ходом Петя может выиграть,
        # то условие задачи будет выполнено, поэтому ИЛИ
        return player2(s + 1, step) or player2(s + 4, step) or player2(s * 2, step)


# ход Вани, результат отвечает на вопрос, удовлетворяется ли
# требование задачи,
# s - кол-во камней в куче, step - номер хода
def player2(s, step):
    # обработка состояния игры после хода Пети
    # если Петя сделал первый ход
    if step == 1:
        # если он при этом победил,
        if s >= 52:
            # требование задачи не выполнено
            return False

        # разные ходы Вани
        # нам нужно, чтобы при любом ходе Вани Петя победил, т.е.
        # требование задачи было выполнено, поэтому используем И
        return player1(s + 1, step + 1) and player1(s + 4, step + 1) and player1(s * 2, step + 1)
    # если Петя сделал второй ход
    else:
        # он должен победить
        return s >= 52


# проверка, может ли Петя выиграть первым ходом
def check(s):
    return s + 1 >= 52 or s + 4 >= 52 or s * 2 >= 52


# перебираем кол-во камней в куче
for s in range(1, 51 + 1):
    # запускаем обработку первого шага Пети, если
    # Петя не может выиграть за один ход и
    # Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня
    if not check(s) and player1(s, 1):
        # выводим кол-во камней во второй куче
        print(s)

Вывод программы:

21
24

Ответ: 21 24

Задание 21

Найдите минимальное значение S, при котором одновременно выполняются два условия:

у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Java
C++
Python

package problem1921;

public class Example6 {


    // ход Пети, результат отвечает на вопрос, выполняется ли первое
    // требование задачи,
    // s - кол-во камней в куче, step - номер хода
    static boolean player1(int s, int step) {
        // если это первый ход Пети, тогда Ваня пока что
        // не сделал ни одного хода
        if (step == 1) {
            // При любом ходе Пети Ваня должен победить,
            // поэтому используем И
            return player2(s + 1, step) &&
                    player2(s + 4, step) &&
                    player2(s * 2, step);

        } else if (step == 2) { // если это второй ход Пети, т.е. Ваня сделал уже один ход
            // если Ваня при этом победил,
            if (s >= 52)
                // требование задачи выполнено
                return true;

            // При любом ходе Пети Ваня должен победить,
            // поэтому используем И
            return player2(s + 1, step) &&
                    player2(s + 4, step) &&
                    player2(s * 2, step);
        } else { // если это третий ход Пети, т.е. Ваня сделал уже два хода
            // если Ваня при этом победил, то требование задачи не выполнено
            return s >= 52;
        }
    }

    // ход Вани, результат отвечает на вопрос, выполняется ли первое
    // требование задачи,
    // s - кол-во камней в куче, step - номер хода
    static boolean player2(int s, int step) {
        // обработка состояния игры после хода Пети
        // если Петя сделал первый ход
        if (step == 1) {
            // если он при этом победил,
            if (s >= 52)
                // требование задачи не выполнено
                return false;

            // разные ходы Вани
            // у Вани есть стратегия, которая позволит ему гарантированно выиграть первым ходом
            // или вторым ходом, т.е. есть хотя бы один ход, ведущий к победе,
            return player1(s + 1, step + 1) ||
                    player1(s + 4, step + 1) ||
                    player1(s * 2, step + 1);
        } else { // если Петя сделал второй ход
            // если он при этом победил,
            if (s >= 52)
                // требование задачи не выполнено
                return false;

            // у Вани есть стратегия, которая позволит ему гарантированно выиграть первым ходом
            // или вторым ходом, т.е. есть хотя бы один ход, ведущий к победе,
            return player1(s + 1, step + 1) ||
                    player1(s + 4, step + 1) ||
                    player1(s * 2, step + 1);
        }
    }


    // ход Пети, результат отвечает на вопрос, выполняется ли второе
    // требование задачи,
    // s - кол-во камней в куче, step - номер хода
    static boolean checkPlayer1(int s, int step) {
        if (step == 1) {
            // При любом ходе Пети Ваня не должен гарантированно победить,
            // поэтому отрицаем выражение и используем И
            return !(checkPlayer2(s + 1, step) &&
                    checkPlayer2(s + 4, step) &&
                    checkPlayer2(s * 2, step));
        } else { // если это второй ход Пети, т.е. Ваня сделал уже один ход
            // если он при этом победил, возвращаем, что условие выполнено
            return s >= 52;
        }
    }

    // ход Вани, результат отвечает на вопрос, выполняется ли второе
    // требование задачи
    // s - кол-во камней в куче, step - номер хода
    static boolean checkPlayer2(int s, int step) {
        // При любом ходе Пети Ваня должен победить,
        // поэтому используем И
        return checkPlayer1(s + 1, step + 1) ||
                checkPlayer1(s + 4, step + 1) ||
                checkPlayer1(s * 2, step + 1);
    }


    public static void main(String[] args) {
        // перебираем кол-во камней в куче
        for (int s = 0; s < 51; s++) {
            // запускаем обработку первого шага Пети, если
            // нас устраивает результат, проверки выполняем отдельными методами
            if (player1(s, 1) && checkPlayer1(s, 1)) {
                // выводим кол-во камней во второй куче
                System.out.println(s);

                break;
            }
        }
    }
}

#include <iostream>


// декларируем метод хода второго игрока
bool player2(int s, int step);

// декларируем метод хода второго игрока
bool checkPlayer2(int s, int step);


// ход Пети, результат отвечает на вопрос, выполняется ли первое
// требование задачи,
// s - кол-во камней в куче, step - номер хода
bool player1(int s, int step) {
    // если это первый ход Пети, тогда Ваня пока что
    // не сделал ни одного хода
    if (step == 1) {
        // При любом ходе Пети Ваня должен победить,
        // поэтому используем И
        return player2(s + 1, step) &&
               player2(s + 4, step) &&
               player2(s * 2, step);

    } else if (step == 2) { // если это второй ход Пети, т.е. Ваня сделал уже один ход
        // если Ваня при этом победил,
        if (s >= 52)
            // требование задачи выполнено
            return true;

        // При любом ходе Пети Ваня должен победить,
        // поэтому используем И
        return player2(s + 1, step) &&
               player2(s + 4, step) &&
               player2(s * 2, step);
    } else { // если это третий ход Пети, т.е. Ваня сделал уже два хода
        // если Ваня при этом победил, то требование задачи не выполнено
        return s >= 52;
    }
}

// ход Вани, результат отвечает на вопрос, выполняется ли первое
// требование задачи,
// s - кол-во камней в куче, step - номер хода
bool player2(int s, int step) {
    // обработка состояния игры после хода Пети
    // если Петя сделал первый ход
    if (step == 1) {
        // если он при этом победил,
        if (s >= 52)
            // требование задачи не выполнено
            return false;

        // разные ходы Вани
        // у Вани есть стратегия, которая позволит ему гарантированно выиграть первым ходом
        // или вторым ходом, т.е. есть хотя бы один ход, ведущий к победе,
        return player1(s + 1, step + 1) ||
               player1(s + 4, step + 1) ||
               player1(s * 2, step + 1);
    } else { // если Петя сделал второй ход
        // если он при этом победил,
        if (s >= 52)
            // требование задачи не выполнено
            return false;

        // у Вани есть стратегия, которая позволит ему гарантированно выиграть первым ходом
        // или вторым ходом, т.е. есть хотя бы один ход, ведущий к победе,
        return player1(s + 1, step + 1) ||
               player1(s + 4, step + 1) ||
               player1(s * 2, step + 1);
    }
}


// ход Пети, результат отвечает на вопрос, выполняется ли второе
// требование задачи,
// s - кол-во камней в куче, step - номер хода
bool checkPlayer1(int s, int step) {
    if (step == 1) {
        // При любом ходе Пети Ваня не должен гарантированно победить,
        // поэтому отрицаем выражение и используем И
        return !(checkPlayer2(s + 1, step) &&
                 checkPlayer2(s + 4, step) &&
                 checkPlayer2(s * 2, step));
    } else { // если это второй ход Пети, т.е. Ваня сделал уже один ход
        // если он при этом победил, возвращаем, что условие выполнено
        return s >= 52;
    }
}

// ход Вани, результат отвечает на вопрос, выполняется ли второе
// требование задачи
// s - кол-во камней в куче, step - номер хода
bool checkPlayer2(int s, int step) {
    // При любом ходе Пети Ваня должен победить,
    // поэтому используем И
    return checkPlayer1(s + 1, step + 1) ||
           checkPlayer1(s + 4, step + 1) ||
           checkPlayer1(s * 2, step + 1);
}


// главный метод программы
int main() {
    // перебираем кол-во камней в куче
    for (int s = 1; s < 69; s++) {
        // запускаем обработку первого шага Пети, если
        // нас устраивает результат,
        if (player1(s, 1) && checkPlayer1(s, 1)) {
            // выводим кол-во камней во второй куче
            std::cout << s << std::endl;
            // завершаем цикл
            break;
        }
    }
    return 0;
}

# ход Пети, результат отвечает на вопрос, выполняется ли первое
# требование задачи,
# s - кол-во камней в куче, step - номер хода
def player1(s, step):
    # если это первый ход Пети, тогда Ваня пока что
    # не сделал ни одного хода
    if step == 1:
        # При любом ходе Пети Ваня должен победить,
        # поэтому используем И
        return player2(s + 1, step) and player2(s + 4, step) and player2(s * 2, step)
    # если это второй ход Пети, т.е. Ваня сделал уже один ход
    elif step == 2:
        # если Ваня при этом победил,
        if s >= 52:
            # требование задачи выполнено
            return True

        # При любом ходе Пети Ваня должен победить,
        # поэтому используем И
        return player2(s + 1, step) and player2(s + 4, step) and player2(s * 2, step)
    # если это третий ход Пети, т.е. Ваня сделал уже два хода
    else:
        # если Ваня при этом победил, то требование задачи не выполнено
        return s >= 52


# ход Вани, результат отвечает на вопрос, выполняется ли первое
# требование задачи,
# s - кол-во камней в куче, step - номер хода
def player2(s, step):
    # обработка состояния игры после хода Пети
    # если Петя сделал первый ход
    if step == 1:
        # если он при этом победил,
        if s >= 52:
            # требование задачи не выполнено
            return False

        # разные ходы Вани
        # у Вани есть стратегия, которая позволит ему гарантированно выиграть первым ходом
        # или вторым ходом, т.е. есть хотя бы один ход, ведущий к победе,
        return player1(s + 1, step + 1) or player1(s + 4, step + 1) or player1(s * 2, step + 1)
    # если Петя сделал второй ход
    else:
        # если он при этом победил,
        if s >= 52:
            # требование задачи не выполнено
            return False

        # у Вани есть стратегия, которая позволит ему гарантированно выиграть первым ходом
        # или вторым ходом, т.е. есть хотя бы один ход, ведущий к победе,
        return player1(s + 1, step + 1) or player1(s + 4, step + 1) or player1(s * 2, step + 1)


# ход Пети, результат отвечает на вопрос, выполняется ли второе
# требование задачи,
# s - кол-во камней в куче, step - номер хода
def checkPlayer1(s, step):
    if step == 1:
        # При любом ходе Пети Ваня не должен гарантированно победить,
        # поэтому отрицаем выражение и используем И
        return not (checkPlayer2(s + 1, step) and checkPlayer2(s + 4, step) and checkPlayer2(s * 2, step))
        # если это второй ход Пети, т.е. Ваня сделал уже один ход
    else:
        # если он при этом победил, возвращаем, что условие выполнено
        return s >= 52

    # ход Вани, результат отвечает на вопрос, выполняется ли второе
    # требование задачи
    # l - кол-во камней в первой куче, r - во второй,  step - номер хода


# ход Вани, результат отвечает на вопрос, выполняется ли второе
# требование задачи
# s - кол-во камней в куче, step - номер хода
def checkPlayer2(s, step):
    # При любом ходе Пети Ваня должен победить,
    #  поэтому используем И
    return checkPlayer1(s + 1, step + 1) or checkPlayer1(s + 4, step + 1) or checkPlayer1(s * 2, step + 1)


# перебираем кол-во камней в куче
for s in range(1, 51 + 1):
    # запускаем обработку первого шага Пети, если
    # нас устраивает результат,
    if player1(s, 1) and checkPlayer1(s, 1):
        # выводим кол-во камней во второй куче
        print(s)
        # завершаем цикл
        break

Вывод программы:

Ответ: 20

Задания для самостоятельного выполнения

Пример 1​

Пример 2​

Пример 1

Пример 2