СтатГрад 2021 аналитическое решение
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
заменить (111, 27)
преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Дана программа для редактора:
НАЧАЛО
ПОКА нашлось (111)
заменить(111, 22)
заменить(222, 11)
КОНЕЦ ПОКА
КОНЕЦ
Известно, что исходная строка содержала более 100 единиц и не содержала других цифр. Укажите минимально возможную длину исходной строки, при которой в результате работы этой программы получится строка, содержащая максимально возможное количество единиц.
Возьмем неограниченное кол-во единиц и выполним над ними несколько шагов алгоритма.
Получается, что из 9 единиц у нас осталось 4. Значит каждые три итерации цикла мы выбрасывали по 5 единиц. Т.к. известно, что исходная строка содержала более 100 единиц и необходимо минимальное количество единиц в исходной строке начнем проверку со 101 единицы.
101/5=20 ост. 1
Откатимся на шаг назад возьмем 6 единиц и проделаем алгоритм вручную.
Получившаяся строка 112. В ней 2 единицы.
Пробуем число 102.
102/5=20 ост. 2
Откатимся на шаг назад возьмем 7 единиц и проделаем алгоритм вручную.
Получившаяся строка 1121. В ней 3 единицы.
Пробуем число 103.
103/5=20 ост. 3
Откатимся на шаг назад возьмем 8 единиц и проделаем алгоритм вручную.
Получившаяся строка 11211. В ней 4 единицы.
Пробуем число 104
104/5=20 ост. 4
Откатимся на шаг назад возьмем 9 единиц и проделаем алгоритм вручную.
Получившаяся строка 221. В ней 1 единица. Пробуем число 105
105/5=21 ост. 0
Откатимся на шаг назад возьмем 5 единиц и проделаем алгоритм вручную.
Получившаяся строка 2211. В ней 2 единицы. Пробуем число 106
106/5=21 ост. 1
В такой ситуации мы уже оказывались, когда брали число 101. Далее наборы единиц и двоек будут повторять те пять, что уже были освещены выше.
112; 1121; 11211; 221; 2211.
Наибольшее количество единиц имеет третий набор, получающийся в том случае, если изначально в строке было 103 единицы.
Ответ: 103
Источник: СтатГрад 2021