Условие задачи
Какая строка получится в результате применения приведенной ниже программы к строке, состоящей из 70 идущих подряд цифр 8? В ответе запишите полученную строку.
Программа работает следующим образом:
- Если находятся четыре двойки, они заменяются на две восьмерки.
- Если находятся четыре восьмерки, они заменяются на две двойки.
- Цикл повторяется до тех пор, пока находятся четыре двойки или четыре восьмерки.
Разбор задачи
Для решения задачи достаточно рассмотреть меньшее количество цифр. Рассмотрим, например, 10 восьмерок: 8888888888.
Применим алгоритм:
- Находим четыре восьмерки. Заменяем их на две двойки. Получаем: 2288888888.
- Снова ищем четыре восьмерки. Заменяем их на две двойки. Получаем: 2222888888.
- Еще раз ищем четыре восьмерки. Заменяем их на две двойки. Получаем: 2222228888.
- И так далее.
Алгоритм сводится к тому, что из восьми восьмерок получается 2 двойки (8 восьмерок → 2 двойки → 1 восьмерка), что означает уменьшение на 6 восьмерок за каждый цикл.
Решение
Имеем 70 восьмерок. Разделим 70 на 6: 70 / 6 = 11 с остатком 4. Алгоритм будет выполнен 11 раз, останется 4 восьмерки.
После 11 циклов останется 4 восьмерки. Применим алгоритм к этим 4 восьмеркам:
- Четыре восьмерки заменяются на две двойки.
В результате применения алгоритма к строке из 70 восьмерок останется строка из двух двоек: 22.