23.07 Количество результатов выполнения программ

Рекурсивное решение

Мы будем использовать рекурсию для перебора всех возможных траекторий команд, учитывая ограничения:

1. Создаём пустое множество A для хранения уникальных результатов.

2. Определяем рекурсивную функцию f(st, count, end_count), где st — текущее число, count — количество применённых команд, end_count — общее количество команд.

3. Если count == end_count, добавляем текущее число st в множество A, так как достигли конца программы.

4. Если команд осталось, проверяем каждую команду и условие кратности 5:

- Если (st + st**2) % 5 != 0, применяем команду прибавить квадрат числа, увеличиваем count на 1.

- Если (st - 12) % 5 != 0, применяем команду вычесть 12, увеличиваем count на 1.

- Если st >= 0 и (st + int(st**0.5)) % 5 != 0, применяем команду прибавить целую часть квадратного корня числа, увеличиваем count на 1.

5. После всех рекурсивных вызовов множество A содержит все уникальные результаты.

# Множество для хранения уникальных результатов
A = set()

# Рекурсивная функция для перебора всех последовательностей команд
def f(st, count, end_count):
    if count == end_count:
        # Добавляем текущее число в множество уникальных результатов
        A.add(st)
    else:
        # Команда прибавить квадрат числа
        if (st + st ** 2) % 5 != 0:
            f(st + st ** 2, count + 1, end_count)
        # Команда вычесть 12
        if (st - 12) % 5 != 0:
            f(st - 12, count + 1, end_count)
        # Команда прибавить целую часть квадратного корня
        if st >= 0:
            if (st + int(st ** 0.5)) % 5 != 0:
                f(st + int(st ** 0.5), count + 1, end_count)

# Запускаем функцию с исходным числом 23 и 5 командами
f(23, 0, 5)

# Выводим количество различных результатов
print(len(A))

Решение через динамику

1. Создаём множество ans с исходным числом 23.

2. Для каждой из 5 команд выполняем следующие шаги:

- Создаём новое множество can_get.

- Для каждого числа i в ans:

* Если (i + i**2) % 5 != 0, добавляем i + i**2 в can_get.

* Если (i - 12) % 5 != 0, добавляем i - 12.

* Если i >= 0 и (i + int(i**0.5)) % 5 != 0, добавляем i + int(i**0.5).

- После обработки всех чисел обновляем ans = can_get.

3. В конце размер множества ans даёт количество уникальных результатов.

# Множество для хранения текущих результатов
ans = set()
ans.add(23)

# Последовательно применяем 5 команд
for operations in range(5):
    can_get = set()
    for i in ans:
        if (i + i ** 2) % 5 != 0:
            can_get.add(i + i ** 2)
        if (i - 12) % 5 != 0:
            can_get.add(i - 12)
        if i >= 0:
            if (i + int(i ** 0.5)) % 5 != 0:
                can_get.add(i + int(i ** 0.5))
    ans = can_get

# Выводим количество различных результатов
print(len(ans))