Question

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах *v* и *w* обозначают цепочки цифр:

- `заменить (v, w)` — заменяет первое вхождение подстроки *v* на *w*;
- `нашлось (v)` — проверяет наличие подстроки *v* в строке.

Дана программа для исполнителя Редактор:

```
НАЧАЛО
  ПОКА нашлось (19) ИЛИ нашлось (299) ИЛИ нашлось (3999)
    ЕСЛИ нашлось (19) ТО
      заменить (19, 2)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (299) ТО
      заменить (299, 3)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (3999) ТО
      заменить (3999, 1)
    КОНЕЦ ЕСЛИ
  КОНЕЦ ПОКА
КОНЕЦ
```

Какая строка получится в результате применения этой программы к строке, состоящей из цифры 1 и 100 идущих подряд цифр 9?

Accepted Answer

39

Answer

Идея решения: отследить, как цикл последовательно применяет три замены, пока в строке присутствует хотя бы одна из трёх подстрок.

Проанализируем логику алгоритма. На каждой итерации цикла выполняются три проверки подряд:
- если есть `19`, заменяем на `2` (удаляем 9);
- если есть `299`, заменяем на `3` (удаляем две 9);
- если есть `3999`, заменяем на `1` (удаляем четыре 9).

Начальная строка: `1` + 100 девяток = `1999...999` (всего 101 символ).

Проследим преобразования:

1. На первой итерации находим `19` в начале, заменяем на `2`: `2999...999` (100 девяток).
2. Теперь ищем `299` — находим, заменяем на `3`: `3999...999` (98 девяток).
3. Ищем `3999` — находим, заменяем на `1`: `1999...999` (94 девятки).

Цикл повторяется. На каждом полном проходе трёх замен удаляется ровно 6 девяток (1 + 2 + 4 = 7 символов заменяются на 1 символ, итого минус 6 девяток).

Исходно 100 девяток. Разделим: $100 = 16 	imes 6 + 4$.

После 16 полных проходов остаётся 4 девятки: `19999`.

Продолжаем:
- `19999` → заменяем `19` на `2` → `2999`;
- `2999` → заменяем `299` на `3` → `39`;
- `39` → нет ни `19`, ни `299`, ни `3999` → цикл завершается.

Проверим с помощью программы:

```python
s = '1' + '9' * 100
while ('19' in s) or ('299' in s) or ('3999' in s):
    if '19' in s:
        s = s.replace('19', '2', 1)
    if '299' in s:
        s = s.replace('299', '3', 1)
    if '3999' in s:
        s = s.replace('3999', '1', 1)
print(s)
```

Результат: `39`.

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