Question

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

1) `заменить (v, w)` — заменяет в строке первое слева вхождение цепочки $v$ на цепочку $w$;
2) `нашлось (v)` — проверяет, встречается ли цепочка $v$ в строке. Возвращает «истина», если встречается, иначе «ложь».

Программа:

```
НАЧАЛО
  ПОКА нашлось (10) ИЛИ нашлось (1)
    ЕСЛИ нашлось (10)
      ТО заменить (10, 001)
      ИНАЧЕ заменить (1, 00)
    КОНЕЦ ЕСЛИ
  КОНЕЦ ПОКА
КОНЕЦ
```

Какая строка получится в результате применения этой программы к строке, состоящей из одной единицы и 75 стоящих справа от неё нулей? В ответе запишите, сколько нулей будет в конечной строке.

Accepted Answer

152

Answer

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

Проанализируем работу алгоритма на примере строки `100`:

- Начало: `100`
- Первая замена `10` → `001`: получаем `0010`
- Вторая замена `10` → `001`: получаем `00001`
- Третья замена `1` → `00`: получаем `000000`

Наблюдение: на каждом шаге цикла (пока есть `10`) к строке добавляются два нуля слева от единицы, а один нуль справа удаляется. Таким образом, количество нулей увеличивается на 1 за каждую замену `10` → `001`. Когда `10` больше не встречается, остаётся одна единица, которая заменяется на два нуля.

Применим логику к исходной строке из одной единицы и 75 нулей:

- Начало: `1` + 75 нулей
- На каждом шаге замены `10` → `001` один нуль справа от единицы переходит влево (в виде двух нулей), а сама единица остаётся. Это продолжается, пока справа от единицы есть нули.
- После 75 таких замен справа от единицы нулей не останется, и строка будет состоять из 150 нулей и одной единицы: `000...000` (150 нулей) + `1`
- Последняя замена `1` → `00`: единица заменяется на два нуля, получаем 152 нуля.

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

```python
s = '1' + '0' * 75
while ('10' in s) or ('1' in s):
    if '10' in s:
        s = s.replace('10', '001', 1)
    else:
        s = s.replace('1', '00', 1)
print(s.count('0'))
```

Программа выводит количество нулей в финальной строке.

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