Question

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

**А) заменить** ($v$, $w$). Эта команда заменяет в строке первое слева вхождение цепочки $v$ на цепочку $w$. Например, выполнение команды **заменить** (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки $v$, то выполнение команды **заменить** ($v$, $w$) не меняет эту строку.

**Б) нашлось** ($v$). Эта команда проверяет, встречается ли цепочка $v$ в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

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

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 68 троек?

```
НАЧАЛО
ПОКА нашлось (999) ИЛИ нашлось (333)
  ЕСЛИ нашлось (333)
    ТО заменить (333, 9)
    ИНАЧЕ заменить (999, 3)
  КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
```

Accepted Answer

93

Answer

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

Начальная строка состоит из 68 троек: `333...333` (68 раз).

Программа работает по следующему принципу: если в строке есть подстрока 333, она заменяется на 9; иначе, если есть 999, она заменяется на 3. Цикл продолжается, пока хотя бы одна из этих подстрок присутствует.

Проследим ключевые этапы:

1. **Начало:** 68 троек = 204 цифры.
   - Каждая замена 333 → 9 уменьшает длину на 2 символа.
   - Каждая замена 999 → 3 уменьшает длину на 2 символа.

2. **Первый этап (замены 333 → 9):**
   - 68 троек содержат 22 полные группы 333 (66 троек) и остаток из 2 троек.
   - После 22 замен: 22 девятки + 2 тройки = `99...99` (22 раз) + `33`.

3. **Второй этап (смешанные замены):**
   - Строка `99...9933` (22 девятки + 2 тройки).
   - Первые 9 девяток образуют 999, заменяются на 3: `333` + 13 девяток + `33`.
   - Три тройки в начале заменяются на 9: `9` + 13 девяток + `33` = 14 девяток + `33`.

4. **Третий этап:**
   - Строка из 14 девяток + `33`.
   - Первые 9 девяток → 3: `3` + 5 девяток + `33` = 6 девяток + `33`.

5. **Четвёртый этап:**
   - Строка из 6 девяток + `33`.
   - 6 девяток не образуют 999, но 333 есть в конце: `999` + `33` → `3` + `33` = `333`.
   - Три тройки заменяются на 9: `9`.

6. **Финальное состояние:**
   - Остаётся `93` (одна девятка и две тройки).

Проверка на Python:

```python
s = '3' * 68
while ('999' in s) or ('333' in s):
    if '333' in s:
        s = s.replace('333', '9', 1)
    else:
        s = s.replace('999', '3', 1)
print(s)
```

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