Задание №19

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

1. Добавить в кучу 100 камней
2. Увеличить число камней в куче в 2 раза

Игра завершается в тот момент, когда количество камней в куче становится не менее 1000. Победителем считается игрок, сделавший последний ход, т.е. первым получивший 1000 или более камней в куче

В начальный момент в куче было S камней ($1 \leq S \leq 999$)
Сколько существует значений S, при которых Ваня гарантированно выигрывает первым ходом?

# Неплохой сайт - https://future-step.ru/tutor/task-19/
# Вообще для объяснения, вероятно, нужно порисовать деревья (для понимания алгоритма достаточно глубины 1 и 2) и разобрать все случаи
# Имеет смысл заучить этот алгоритм, ибо он универсален, а при выводе на месте можно ошибиться

def can_win(x, depth):
    '''
        Рекурсивная проверка возможности победы

        Args:
            x (int): число камней в куче на момент хода
            depth (int): сколько ходов осталось
        Returns:
            bool: True если гарантировано можно, иначе False 
    '''
    # Если куча заполнилась на прошлом ходу, то прошлый игрок победил
    if x >= 1000:
        # Выжный момент: 
        # Если изначальное число ходов было чётным, то выполнение условия означает, что победил Ваня
        # Если изначальное число ходов было нечётным, то выполнение условия означает, что победил Петя
        # Такое поведение и позволяет коду работать для любого из игроков
        return depth % 2 == 0

    # Если ходы кончились, но куча всё ещё не заполнена - все проиграли
    if depth == 0:
        return False

    # Создаём массив из всевозможных ходов
    moves = [
        can_win(x + 100, depth - 1),
        can_win(x * 2, depth - 1)
    ]

    # Хотябы один путь должен вести к победе, если это наш ход, а если соперника - то должны вести все
    #
    # [наш ход] if depth % 2 == 1 else [ход сопрерника]
    # Если не до конца понятен синтаксис, то можно подробнее найти информацию по запросу `тернарный оператор python` 
    #
    # Подробное пояснение:
    # Если изначальное число ходов было чётным (т.е. мы проверяем, может ли Ваня гарантированно победить), то
    #     на чётной глубине (ходах Пети), нужно чтобы все ходы вели к победе - здесь работает ветка all(moves)
    #     на нечётной глубине (ходах Вани), нужно чтобы хотя бы один ход вёл к победе - здесь работает ветка any(moves)
    # Если изначальное число ходов было нечётным (т.е. мы проверем, может ли Петя гарантированно победить), то
    #     на нечётной глубине (ходах Пети), нужно чтобы хотя бы один ход вёл к победе - здесь работает ветка any(moves)
    #     на чётной глубине (ходах Вани),  нужно чтобы все ходы вели к победе - здесь работает ветка all(moves)
    return any(moves) if depth % 2 == 1 else all(moves)

# Счётчик побед Вани
count = 0

# Перибераем все размеры кучи от 1 до 999
# К правой границе прибавляем 1 т.к. встроенный range не включает в себя правую границу
# Синтаксис range: range([левая граница включительно], [правая граница исключительно])
for S in range(1, 999 + 1):
    if can_win(S, 2) and not can_win(S, 1):
        count += 1

print(count)

100

Задание №20

Сколько существует значений S, при которых Петя может выиграть своим вторым ходом

# Счётчик побед Пети
count = 0

# Перибераем все размеры кучи от 1 до 999
# К правой границе прибавляем 1 т.к. встроенный range не включает в себя правую границу
# Синтаксис range: range([левая граница включительно], [правая граница исключительно])
for S in range(1, 999 + 1):
    # Из условия:
    #     Петя должен победить за 2 хода
    # и одновременно
    #     Петя не должен победить за 1 ход
    if can_win(S, 3) and not can_win(S, 1):
        count += 1

print(count)

150

Задание №21

Для задачи 19 назовите минимальное и максимальное значение S, при котрых Ваня выигрывает своим в первым или вторым ходом, при этом для любого значения у Вани есть возможность выиграть своим первым ходом (в случае ошибки Пети)

# Примечание: из условия не до конца ясно, нужно ли запрещать ване побеждать своим первым ходом.
# Я считаю, что нет, однако трактовать формулировку можно по разному

# Список подходящих значений
values = []

# Перибераем все размеры кучи от 1 до 999
# К правой границе прибавляем 1 т.к. встроенный range не включает в себя правую границу
# Синтаксис range: range([левая граница включительно], [правая граница исключительно])
for S in range(1, 999 + 1):
    # Из условия:
    #     Ваня должен победить за 2 хода (включает в сеобя пути победы за 1 ход)
    # и одновременно
    #     Ваня должен иметь возможность победить после одного хода Пети
    #         (я несколько затрудняюсь объяснить `на пальцах` почему условие (can_win(S + 100, 1) or can_win(S*2, 1)) равносильно утверждению выше,
    #         но если посмотреть, как исполняется функция, то это действительно будет работать)
    if (can_win(S, 4)) and (can_win(S + 100, 1) or can_win(S*2, 1)):
        values.append(S)

print(values[0], values[-1])

250 499

Задание №25

Среди натуральных чисел, не превышающих $10^{10}$, найдите все числа, соответствующие маске «4*25*6?77», делящиеся на 2907 без остатка.
В ответ запишите в первом столбце таблицы четыре наибольщих числа в порядке убывания, а во втором столбце - соответствующие результаты деления этих чисел не 2907

# Импортируем стандартную библиотеку для работы с масками
# (на что отсылает название библиотеки - re - Regular Expressions - регулярные выражения)
import re

# Создаём шаблон для проверки
# . - место для одного любого символа
# * - символ, идущий до звёздочки должен повотряться от 0 до бесконечного числа раз
# Поиграться с регулярными выражениями можно на https://regex101.com/ только не забудьте выбрать python как язык
# P.S. нашёл ещё неплохой интерактивный учбник - https://regexlearn.com/ru/learn/regex101 вероятно это уже слишком для ЕГЭ, но это даёт чуть больше глубины понимания
pattern = re.compile("4.*25.*6.77")

# Создаём пустой массив для подошедших чисел
result = []

# Перибераем все числа в диапазоне от 2907 до 10^10 с шагом 2907
# Это не нужно делать полным перебором всех чисел, ибо тогда исполнение будет очень долгим
# К верхней границе прибавляем 1 т.к. встроенный range не включает в себя правую границу
# Синтаксис range: range([левая граница включительно], [правая граница исключительно], [шаг])
for number in range(2907, 10**10 + 1, 2907):
    # Проверяем, подходит ли число под шаблон
    # (на что и намекает название функции fullmatch - полное совпадение)
    # Также необходимо привести число к строковому типу (функция str), ибо fullmatch работает с ними и только с ними
    if re.fullmatch(pattern, str(number)):
        # Добавляем число в конец массива результатов
        result.append(number)

# Делаем срез массива
# от -4 - начиная с 4 элемента с конца
# до '' - границу обычно опускают, если нужно получить срез массива до самого его конца
# Массив уже отсортирован (т.к. мы добавляли числа по возрастанию), так что дополнительная сортировка не нужна
largest_4 = result[-4:]

# Упорядочиваем полученные числа по убыванию
largest_4.reverse()

# Проходимся по числам в массиве и выводим результат
for number in largest_4:
    # Используем // для операции целочисленного деления (чтобы небыло .0 на конце, как у float)
    print(number, number//2907)

4869256977 1675011
4844256777 1666411
4819256577 1657811
4794256377 1649211