19-21

#include <iostream>

using namespace std;
// на основе этого видео https://youtu.be/hSbDxT8i1uY

// написано для задачи 35 Полякова 2021

// функция для 19-й задачи
bool f19 (int x, int y, int p) {
    // P - позиция
    //    0     1     2     3     4
    // (7; s)  Петя  Ваня  Петя  Ваня
    if (x + y >= 61 && p == 2) {
        return true;
    }
    // если мы находимся на нужном ходе (P), а сумма меньше нужной,
    // то возвращаем false, т.к. это нам не подходит
    else {
        if (x + y < 61 && p == 2) {
            return false;
        }
    }
    // рекурсивно вызываем все возможные ходы
    return f19(x + 1, y, p + 1) || f19(x * 2, y, p + 1) || f19(x, y + 1, p + 1) || f19(x, y * 2, p + 1);
}

// преобразуем эту же функцию для 20-й задачи
bool f20(int x, int y, int p) {
    // меняем P на нужное
    if (x + y >= 61 && p == 3) {
        return true;
    }
    else {
        // меняем P
        if (x + y < 61 && p == 3) {
            return false;
        }
        else {
            // сумма больше нужной, а P нам не подходит (иначе сработало бы первое условие)
            // возвращаем false
            if (x + y >= 61) {
                return false;
            }
        }
    }
    // Петя выигрывает вторым ходом независимо от хода Вани,
    // поэтому все ходы Пети после Вани должны быть true
    // ходы Пети нечётные P = 1, 3, 5
    // поэтому оператор И используем на ходах Пети, где значения P нечётные
    // эту часть важно хорошо понимать - если неправильно написать условие,
    // то программа либо ничего не выведет, либо выведет неправильные значения (их будет больше двух)
    if (p % 2 != 0) // P должно "принадлежать" Пете
        return f20(x + 1, y, p + 1) && f20(x * 2, y, p + 1) && f20(x, y + 1, p + 1) && f20(x, y * 2, p + 1);
    else
        return f20(x + 1, y, p + 1) || f20(x * 2, y, p + 1) || f20(x, y + 1, p + 1) || f20(x, y * 2, p + 1);

}

// преобразуем предыдущую функцию для 21-й задачи
bool f21 (int x, int y, int p) {
    // у нас теперь два P
    if ((x + y >= 61 && p == 2) ||(x + y >= 61 && p == 4)) {
        return true;
    }
    else {
        // проверяем до конца, поэтому P == 4, а не 2
        if (x + y < 61 && p == 4) {
            return false;
        }
        else {
            if (x + y >= 61) {
                return false;
            }
        }
    }
    // теперь Ваня побеждает при любом ходе Пети,
    // поэтому при чётных ходах (ходах Вани) используем оператор ИЛИ
    // а при нечётных ходах (ходах Пети) оператор И
    if (p % 2 == 0) // тут Ваня
        return f21(x + 1, y, p + 1) && f21(x * 2, y, p + 1) && f21(x, y + 1, p + 1) && f21(x, y * 2, p + 1);
    else
        return f21(x + 1, y, p + 1) || f21(x * 2, y, p + 1) || f21(x, y + 1, p + 1) || f21(x, y * 2, p + 1);
}

// проверяем, есть ли такие S, которые работают только для P == 3 (если есть, то они нам не подходят - вычитаем)
// просто копируем предыдущую функцию
bool f21d (int x, int y, int p) {
    // оставляем только P == 3
    if (x + y >= 61 && p == 3) {
        return true;
    }
    else {
        // проверяем до P == 3
        if (x + y < 61 && p == 3) {
            return false;
        }
        else {
            if (x + y >= 61) {
                return false;
            }
        }
    }
    // оставляем как в предыдущей функции
    if (p % 2 == 0)
        return f21(x + 1, y, p + 1) && f21(x * 2, y, p + 1) && f21(x, y + 1, p + 1) && f21(x, y * 2, p + 1);
    else
        return f21(x + 1, y, p + 1) || f21(x * 2, y, p + 1) || f21(x, y + 1, p + 1) || f21(x, y * 2, p + 1);
}

int main() {
    cout << "19: ";
    for (int i = 1; i <= 53; i++) {
        // выводим первое значение (минимальное), которое нам подходит
        if (f19(7, i, 0)) {
            cout << i << endl;
            break;
        }
    }
    cout << "20: ";
    for (int i = 1; i <= 53; i++) {
        // выводим все значения
        if (f20(7, i, 0)) {
            cout << i << " ";
        }
    }
    cout << endl << "21: ";
    for (int i = 1; i <= 53; i++) {
        if (f21(7, i, 0)) {
            cout << i << " ";
        }
    }
    cout << endl << "Не подходят для 21: ";
    // если программа тут что-то находит, то это число нам не подходит
    for (int i = 1; i <= 53; i++) {
        if (f21d(7, i, 0)) {
            cout << i << " ";
        }
    }
}