Задание №12 — Анализ строковых алгоритмов

#69250Задание №12ФИПИ

Анализ алгоритмов и исполнители

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Цикл
    ПОКА условие
        последовательность команд
    КОНЕЦ ПОКА
выполняется, пока условие истинно.

В конструкции
   ЕСЛИ условие
      ТО команда1
      ИНАЧЕ команда2
   КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>0)
   ЕСЛИ нашлось (>1)
      ТО заменить (>1, 22>)
   КОНЕЦ ЕСЛИ
   ЕСЛИ нашлось (>2)
      ТО заменить (>2, 2>)
   КОНЕЦ ЕСЛИ
   ЕСЛИ нашлось (>0)
      ТО заменить (>0, 1>)
   КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с символа «>», а затем содержащая 39 цифр «0», n цифр «1» и 39 цифр «2», расположенных в произвольном порядке. Определите наименьшее значение n, при котором сумма числовых значений цифр строки, получившейся в результате выполнения программы, является
простым числом.

Правильный ответ

Пояснение

Решение:

В строке ровно один символ «>». Все три замены имеют вид «> и цифра» → «цифры и >», то есть символ «>» движется слева направо и по дороге переписывает каждую цифру, мимо которой проходит:

>0 → 1> — цифра 0 превращается в 1, вклад в сумму равен 1;
>1 → 22> — цифра 1 превращается в две двойки, вклад в сумму равен 4;
>2 → 2> — цифра 2 не меняется, вклад в сумму равен 2.

Новые цифры оказываются левее символа «>», поэтому повторно они не обрабатываются. Значит, порядок цифр во входной строке не важен, а итоговая сумма цифр равна

$S(n) = 39\cdot 1 + n\cdot 4 + 39\cdot 2 = 117 + 4n.$

Ищем наименьшее $n$ , при котором $117+4n$ — простое число:

$n=0:\ 117 = 9\cdot 13$ — составное;
$n=1:\ 121 = 11^2$ — составное;
$n=2:\ 125 = 5^3$ — составное;
$n=3:\ 129 = 3\cdot 43$ — составное;
$n=4:\ 133 = 7\cdot 19$ — составное;
$n=5:\ 137$ — простое.

Проверка программой:

def run(s):
    while '>1' in s or '>2' in s or '>0' in s:
        if '>1' in s:
            s = s.replace('>1', '22>', 1)
        if '>2' in s:
            s = s.replace('>2', '2>', 1)
        if '>0' in s:
            s = s.replace('>0', '1>', 1)
    return s
def prime(k):
    return k > 1 and all(k % d for d in range(2, int(k ** 0.5) + 1))
for n in range(0, 100):
    s = run('>' + '0' * 39 + '1' * n + '2' * 39)
    if prime(sum(int(c) for c in s if c.isdigit())):
        print(n)      # 5
        break

Ответ: 5