12.04 Исполнитель «Редактор» – прочие прототипы

Решение 1

Распишем все переходы для пар из единиц и двоек.

Задача у нас про сумму цифр, как видим сумма при переходе пар константна.

Рассмотрим переходы одиночных цифр между нулями.

Как видим, сумма оба раза уменьшилась на единицу. Получается, что если изначальная сумма была , то сумма после работы алгоритма будет , однако если не допустить этих оперпций, то сумма не изменится и так потребуется меньшее количество единиц. Это можно сделать поставив после нуля 25 двоек, затем все единицы, и снова 25 двоек. Начальная сумма цифр . Нам необходимо количество единиц . Минимальное простое число большее — это , получаем — количество единиц.

Решение 2

def is_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return n > 1

for n in range(101, 1000):
    s = "0" + ’2’ * 25 + ’1’ * n + ’2’ * 25 + ’0’
    while not (’00’ in s):
        s = s.replace(’02’, ’101’, 1)\
            .replace(’11’, ’2’, 1)\
            .replace(’012’, ’30’, 1)\
            .replace(’010’, ’00’, 1)
    if is_prime(sum(int(x) for x in s)):
        print(n)
        break