Question

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах *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*, при котором сумма числовых значений цифр строки, получившейся в результате выполнения программы, является простым числом.

Accepted Answer

5

Answer

Идея решения: проанализировать, как программа преобразует строку, вычислить итоговую сумму цифр в зависимости от *n*, и найти минимальное *n*, при котором эта сумма — простое число.

**Анализ преобразований:**

Программа выполняет замены в цикле:
- `>1` заменяется на `22>` (цифра 1 становится двумя цифрами 2)
- `>2` заменяется на `2>` (цифра 2 остаётся, но символ `>` сдвигается)
- `>0` заменяется на `1>` (цифра 0 становится цифрой 1)

Цикл продолжается, пока в строке есть хотя бы одна из подстрок `>1`, `>2` или `>0`.

**Вычисление итоговой суммы:**

После полного выполнения программы:
- Все 39 нулей превратятся в единицы (каждый ноль добавляет 1 к сумме).
- Все 39 двоек останутся двойками (каждая двойка добавляет 2 к сумме).
- Каждая из *n* единиц превратится в две двойки (каждая единица добавляет $2 	imes 2 = 4$ к сумме).

Итоговая сумма: $S(n) = 39 	imes 1 + 39 	imes 2 + n 	imes 4 = 39 + 78 + 4n = 117 + 4n$.

**Поиск минимального *n*:**

Нужно найти наименьшее *n* такое, что $117 + 4n$ — простое число.

Проверим значения:
- $n = 0$: $S = 117 = 9 	imes 13$ (не простое)
- $n = 1$: $S = 121 = 11^2$ (не простое)
- $n = 2$: $S = 125 = 5^3$ (не простое)
- $n = 3$: $S = 129 = 3 	imes 43$ (не простое)
- $n = 4$: $S = 133 = 7 	imes 19$ (не простое)
- $n = 5$: $S = 137$ (простое число)

Проверим, что 137 простое: оно не делится на 2, 3, 5, 7, 11 и не имеет делителей до $\sqrt{137} \approx 11{,}7$.

```python
def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

n = 0
while True:
    s = 117 + 4 * n
    if is_prime(s):
        print(n)
        break
    n += 1
```

Задание №12Алгоритмы и исполнителиЕГЭ по информатике