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

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

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

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

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

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

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

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

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

Пояснение

Решение:

Символ «>» работает как указатель, который движется по строке слева направо. Каждая замена берёт цифру, стоящую сразу за указателем, и записывает результат слева от «>», то есть обработанная часть строки больше не меняется:

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

Каждая цифра исходной строки обрабатывается ровно один раз, поэтому порядок цифр не важен, а сумма цифр результата равна $15 \cdot 4 + n \cdot 2 + 15 \cdot 1 = 75 + 2n.$

Осталось перебрать $n$ : при $n=1$ сумма $77 = 7 \cdot 11$ — составное число; при $n=2$ сумма $79$ — простое. Наименьшее подходящее значение $n = 2$ .

def zamenit(s, v, w):
    return s.replace(v, w, 1)   # первое слева вхождение

def prostoe(x):
    d = 2
    while d * d <= x:
        if x % d == 0:
            return False
        d += 1
    return x > 1

def rabota(s):
    while ">0" in s or ">1" in s or ">2" in s:
        if ">0" in s:
            s = zamenit(s, ">0", "22>")
        if ">1" in s:
            s = zamenit(s, ">1", "2>")
        if ">2" in s:
            s = zamenit(s, ">2", "1>")
    return s

n = 1
while True:
    s = rabota(">" + "0" * 15 + "1" * n + "2" * 15)
    summa = sum(int(c) for c in s if c != ">")
    if prostoe(summa):
        print(n, summa)   # 2 79
        break
    n += 1

Ответ: 2