ЕГЭ–2026, информатика: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 12 № 63061 Добавить в вариант

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

А)  заменить (v, w).

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

Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б)  нашлось (v).

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

Дана программа для редактора:

НАЧАЛО

                ПОКА НЕ нашлось (00)

                        заменить (01, 220)

                        заменить (02, 1013)

                        заменить (03, 120)

                КОНЕЦ ПОКА

КОНЕЦ

Известно, что в исходной строке A было ровно два нуля  — на первом и на последнем месте, а после выполнения данной программы получилась строка B, содержащая 13 единиц и 18 двоек.

Какое наименьшее количество цифр могло быть в строке A?

Спрятать решение

Решение.

Приведём решение на языке Python.

A = []

for x in range(20,-1,-1):

for y in range(20,-1,-1):

for z in range(20,-1,-1):

num = '0' + '1'*x + '2'*y + '3'*z +'0'

while '00' not in num:

num = num.replace('01','220',1)

num = num.replace('02','1013',1)

num = num.replace('03','120',1)

if num.count('1') == 13 and num.count('2') == 18:

A.append(x + y + z)

print(min(A) + 2)

Ответ: 10.

Приведём аналитическое решение Юрия Красильникова.

В алгоритме выполняются следующие замены:

01->220

02->1013->12203->122120

03->120

Каждая единица превращается в выходной строке в две двойки, двойка  — в две единицы и три двойки, а тройка  — в единицу и двойку.

Если во входной строке было x единиц, y двоек и z троек, то в выходной строке будет 2y + z единиц, 2x + 3y + z двоек и 0 троек.

Имеем систему из двух уравнений с тремя неизвестными: $2 y плюс z = 13.$ Тогда $2 x плюс 3 y плюс z = 18,$ где x, y, z  — целые неотрицательные числа.

Если вычесть из нижнего уравнения верхнее, получим $2 x плюс y = 5.$

Данное уравнение имеет всего три решения в неотрицательных целых числах: x  =  0, y  =  5; x  =  1, y  =  3; x  =  2, y  =  1.

Из верхнего уравнения можно выразить z  =  13 − 2y.

Имеем решения x  =  0, y  =  5, z  =  3; x  =  1, y  =  3, z  =  7; x  =  2, y  =  1, z  =  11.

Наименьшая сумма x + y + z  =  8  — в первом решении.

Учитывая два нуля в начале и конце исходной строки, получаем ответ: 10.

Аналоги к заданию № 63028: 63061 Все

Спрятать решение · Прототип задания · Помощь