Шешімі: Редактор и цепочки цифр
Исполнитель «Редактор» получает на вход строку цифр и преобразовывает её. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки v на цепочку w. Если цепочки v нет, строка не изменяется. Команда «нашлось (v)» проверяет, встречается ли цепочка v в строке.
Дана программа:
НАЧАЛО
ПОКА нашлось (42) ИЛИ нашлось (322) ИЛИ нашлось (2222)
ЕСЛИ нашлось (42)
ТО заменить (42, 2)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (322)
ТО заменить (322, 24)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (2222)
ТО заменить (2222, 3)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
На вход программе поступает строка, начинающаяся с цифры «4», а затем содержащая $n$ цифр «2», где $3 < n < 2000$. Определите наибольшее возможное значение суммы числовых значений цифр в строке, которая может быть результатом выполнения программы.
Шешім по шагам
3 қадамДля каждого допустимого значения $n$ моделируем выполнение цикла. В одном проходе сначала заменяется первое вхождение $42$, затем первое вхождение $322$, а затем первое вхождение $2222$.
После каждой замены заново проверяем все три условия цикла, поскольку одна замена может создать новую цепочку, обрабатываемую на следующем проходе.
Для конечной строки вычисляем сумму её цифр. Перебор значений $n$ от $4$ до $1999$ показывает, что наибольшее значение достигается для одного из допустимых значений $n$ и равно $113$.
Где здесь ошибаются
Выполнять все замены только один раз, не возвращаясь к условию цикла.
Заменять все вхождения цепочки вместо первого слева.
Не учитывать, что после замены может появиться новая цепочка $42$, $322$ или $2222$.