Question

Исполнитель Редактор получает на вход строку цифр и преобразует её с помощью двух команд:

**А) заменить** (*v*, *w*) — заменяет в строке первое слева вхождение цепочки *v* на цепочку *w*. Если *v* не встречается, строка не меняется.

**Б) нашлось** (*v*) — проверяет наличие цепочки *v* в строке (возвращает истину или ложь, строка не изменяется).

Цикл **ПОКА** условие выполняется, пока условие истинно. Конструкция **ЕСЛИ** условие **ТО** команда1 **КОНЕЦ ЕСЛИ** выполняет команду1 при истинности условия.

Редактор получает строку, начинающуюся с 3 и содержащую далее *n* пятёрок (5), где *n* > 3. Программа:

```
НАЧАЛО
ПОКА нашлось (25) ИЛИ нашлось (355) ИЛИ нашлось (555)
  ЕСЛИ нашлось (25) ТО заменить (25, 3) КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (355) ТО заменить (355, 52) КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (555) ТО заменить (555, 23) КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
```

Найдите минимальное значение *n*, при котором сумма цифр конечной строки равна 27.

Accepted Answer

16

Answer

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

Программа выполняет замены в цикле до тех пор, пока в строке присутствует хотя бы одна из подстрок: 25, 355 или 555. На каждой итерации проверяются условия по порядку и выполняются соответствующие замены (первое вхождение).

Ключевое наблюдение: каждая замена изменяет сумму цифр строки:
- замена 25 на 3: сумма уменьшается на $2 + 5 - 3 = 4$;
- замена 355 на 52: сумма уменьшается на $3 + 5 + 5 - 5 - 2 = 6$;
- замена 555 на 23: сумма уменьшается на $5 + 5 + 5 - 2 - 3 = 10$.

Начальная сумма для строки «3» + *n* пятёрок равна $3 + 5n$.

Переберём значения *n* от 4 до 100, для каждого смоделируем преобразования и проверим, когда сумма цифр результата станет равна 27:

```python
for n in range(4, 100):
    s = '3' + '5' * n
    while ('25' in s) or ('355' in s) or ('555' in s):
        s = s.replace('25', '3', 1)
        s = s.replace('355', '52', 1)
        s = s.replace('555', '23', 1)
    digit_sum = 2 * s.count('2') + 3 * s.count('3') + 5 * s.count('5')
    if digit_sum == 27:
        print(n)
        break
```

Программа перебирает *n* и для каждого значения:
1. Инициализирует строку как «3» + *n* пятёрок.
2. Выполняет цикл замен, пока в строке есть хотя бы одна из трёх подстрок.
3. Вычисляет сумму цифр: $2 	imes 	ext{(кол-во двоек)} + 3 	imes 	ext{(кол-во троек)} + 5 	imes 	ext{(кол-во пятёрок)}$.
4. Если сумма равна 27, выводит *n* и завершает поиск.

При *n* = 16 начальная строка — «3555555555555555555» (3 и 16 пятёрок). После всех замен получается строка, сумма цифр которой равна 27.

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