какое максимально возможное количество единиц может находиться в строке после применения

Какое максимально возможное количество единиц может находиться в строке после применения

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

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды

преобразует строку 05111150 в строку 0527150.

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

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

исполнителя при этом не изменяется.

выполняется, пока условие истинно.

выполняется команда1 (если условие истинно).

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

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

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

Заметим, что алгоритм заменяет 9 единиц на 2 единицы. То есть если в исходной строке как минимум 9 единиц, то за три прохода количество единиц уменьшится на 7.

Заметим, что строка 221 получается из исходной строки, состоящей из семи единиц. Наибольшее число, кратное 7 и меньшее 60 — 56. Таким образом, наименьшее количество единиц, которое могло быть в исходной строке, равно 56 + 7 = 63.

Источник

Какое максимально возможное количество единиц может находиться в строке после применения

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

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды

преобразует строку 05111150 в строку 0527150.

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

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

исполнителя при этом не изменяется.

выполняется, пока условие истинно.

выполняется команда1 (если условие истинно).

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

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

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

Заметим, что алгоритм заменяет 9 единиц на 2 единицы. То есть если в исходной строке как минимум 9 единиц, то за три прохода количество единиц уменьшится на 7.

Заметим, что строка 2211 получается из исходной строки, состоящей из восьми единиц. Наибольшее число, кратное 7 и меньшее 60 — 56. Таким образом, наименьшее количество единиц, которое могло быть в исходной строке, равно 56 + 8 = 64.

Источник

12 задание ЕГЭ по информатике: разбираем все прототипы

Татьяна Задоля

12 задание ЕГЭ по информатике обычно решает только половина выпускников. Оно правда такое сложное? Нет, если заранее изучить каждый из трех прототипов. Из этой статьи вы узнаете, как справиться с Редактором, Роботом и Чертежником — и как можно сделать это еще проще, используя программирование.

Прототипы задания 12 и их сложности

12 задание ЕГЭ по информатике относится к повышенному уровню сложности. На экзамене за него можно получить один первичный балл.

Это задание — часть блога «Алгоритмизация». Чтобы решить его, нужно уметь работать с алгоритмами и анализировать их. В этом задании могут встретиться три прототипа заданий: Редактор, Робот и Чертежник. Причем Редактор встречается на экзамене в последнее время чаще других прототипов.

Редактор — это прототип на работу с цепочками цифр или букв. Нам дают алгоритм и строку, содержащую некоторое количество знаков. Нужно узнать, какая строка получится после выполнения программы или посчитать количество символов в строке.

Если решать подобные задания аналитически, нужно искать закономерности изменения цепочки, чтобы получить ответ. Именно в этом и заключается сложность задания, ведь не все могут правильно найти нужную закономерность.

Робот — прототип на работу с клетчатой плоскостью и алгоритмом. Вам дают алгоритм и плоскость, содержащую 36 клеток. Нужно найти количество клеток, удовлетворяющее определенному условию. Сложность в том, что ученики начинают проверять все 36 клеток. Делать это не нужно, если проанализировать алгоритм из условия.

Чертежник — прототип на работу с алгоритмом, где исполнитель перемещается по координатной плоскости. Чаще всего в таких заданиях в алгоритме есть пропуски в командах. Нужно найти наибольшее количество повторений цикла. Сложностей обычно здесь не так много, основная — невнимательность при выполнении вычислений.

Самостоятельно подготовиться к ЕГЭ непросто. На то, чтобы разобраться со всеми темами, понадобится много времени. Но и это не решит проблему! Например, если вы запомнили какое-то решение из интернета, а оно оказалось неправильным, можно на пустом месте потерять баллы. Если хотите научиться решать все задания ЕГЭ по информатике, обратите внимание на онлайн-курсы MAXIMUM! Наши специалисты уже проанализировали сотни вариантов ЕГЭ и подготовили для вас вас максимально полезные занятия.

Приходите к нам на консультацию — вы сможете пройти диагностику по выбранным предметам ЕГЭ, поставить цели и составить стратегию подготовки, чтобы получить на экзамене высокие баллы. Все это абсолютно бесплатно!

Редактор — как решать?

Задания с прототипом «Редактор» можно решать как аналитически, так и с помощью компьютера, если у вас все хорошо с программированием. Мы рассмотрим с вами оба способа решения и убедимся, что они дают одинаковые ответы.

Пример 1 (Редактор)

Исполнитель Редактор получает на вход строку цифр и преобразовывает ее.

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

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

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

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

Какая строка получится в результате применения приведенной ниже программы к строке, состоящей из 88 идущих подряд цифр 4? В ответе запишите полученную строку.

Аналитическое решение

Алгоритм сначала заменяет в цепочке цифр все четверки на единицы. Потом начинает заменять назад единицы на четверки, но как только в цепочке образуются 3 четверки, алгоритм заменяет их на единицу. Порядок замены имеет значение при поиске ответа, поэтому его нужно обязательно учитывать. Также важно, что замена выполняется всегда в начале цепочки.

Сначала уберем по возможности все четверки из цепочки.

88 / 3 = 29 и 1 в остатке.

Получается, что из цепочки уйдет 29 блоков по 3 четверки и образуется 29 единиц, 1 четверка останется в цепочке в самом конце.

Теперь будем последовательно убирать единицы из цепочки.

Как только в цепочке появились 3 четверки, алгоритм заменил их назад на единицу. Суммарно из цепочки ушло 5 единиц. Это действие будет повторяться циклически, поэтому можно посчитать, сколько блоков по 5 единиц уйдет из цепочки.

29 / 5 = 5 и 4 в остатке

Получается, что в цепочке останется 4 единицы и 1 четверка.

11114 → 4114 → 444 → 1

В итоге в цепочке останется только единица.

Решение с помощью компьютера

В самом задании у нас уже написана программа. Остается перевести ее на конкретный язык программирования. Напишем программу на Python.

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

Создаем строку, содержащую 88 четверок. Далее запускаем цикл, который будет проверять, есть ли в строке 3 четверки или 2 единицы. Пропиваем условие и замену в строке. Важно в методе replace() указать третий параметр, который отмечает, сколько замен нужно выполнить. По умолчанию replace() сразу заменит все цифры в строке, а нам нужно выполнять замены по одной.

При запуске данной программы мы также получим ответ 1.

Ответ: 1

Пример 2 (Редактор)

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

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

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

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

На вход приведенной ниже программе поступает строка, начинающаяся с символа «>», а затем содержащая 25 цифр 1, 45 цифр 2 и 10 цифр 3, расположенных в произвольном порядке.

Определите сумму числовых значений цифр строки, получившейся в результате выполнения программы.

Так, например, если результат работы программы представлял бы собой строку, состоящую из 50 цифр 4, то верным ответом было бы число 200.

Аналитическое решение

Цифры 1, 2 и 3 находятся в строке в произвольном порядке. Все, что нам нужно сделать, чтобы получить ответ — это понять, сколько цифр образовалось в результате замен.

Каждую единицу алгоритм заменит на тройку. Если изначально было 25 единиц, то в результате замен образуется 25 троек, и их сумма будет равна 25 * 3 = 75.

Каждую двойку алгоритм заменит на 2 единицы. Изначально было 45 двоек, значит, в результате замен образуется 90 единиц. Их сумма будет равна 90.

Каждую тройку алгоритм заменит на 2 тройки. Было 10 троек, станет 20. Сумма составит 20 * 3 = 60.

Итоговая сумма всех цифр цепочки будет равна 75 + 90 + 60 = 225.

Решение с помощью компьютера

Перенесем алгоритм на язык программирования Python.

Получаем следующую программу:

Сначала мы задали строку, содержащую знак “>” и нужное количество всех цифр. Далее в цикле проверяем наличие знака “>” и цифр и выполняем замену. Как только программа вышла из цикла, считаем количество единиц, двоек и троек в строке — и находим сумму. При запуске программы также получается ответ 225.

В данном задании написание программы может занять больше времени, чем аналитическое решение. Поэтому всегда оценивайте временные затраты на написание кода.

Ответ: 225

Робот — как решать?

Второй прототип, который включает в себя 12 задание ЕГЭ по информатике — Робот. Этот прототип точно придётся решать аналитически, поэтому давайте разбираться, как сделать это с минимальными затратами времени.

Пример 3 (Робот)

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, включает в себя 4 команды-приказа и 4 команды проверки условия.

Команды-приказы: вверх, вниз, влево, вправо

При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →.

Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится, и программа прервется.

Другие 4 команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: сверху свободно, снизу свободно, слева свободно, справа свободно

Цикл

Выполняется, пока условие истинно, иначе происходит переход на следующую строку.

Если РОБОТ начнет движение в сторону стены, то он разрушится, и программа прервется.

Сколько клеток лабиринта соответствуют требованию, что, выполнив предложенную программу, РОБОТ уцелеет и остановится в той же клетке, с которой он начал движение?

ПОКА вправо

ПОКА вверх

ПОКА влево

ПОКА вниз

Решение

Чтобы не проверять все 36 клеток плоскости, нужно проанализировать программу. В алгоритме 4 цикла, но нам важен только последний. Робот будет выполнять действия и остановится только в той клетке плоскости, где слева есть стена, так как в последнем цикле мы проверяем именно это условие. Поэтому необходимо проверить только те клетки, где слева есть стена. В остальных клетках плоскости Робот просто не сможет остановиться, поэтому и начинать движение из них мы тоже не будем.

Проверяем по алгоритму 12 отмеченных клеток.

Из всех отмеченных клеток нам подойдет только клетка В5. Если начать движение из нее, Робот вернется в эту же точку. Остальные клетки не подойдут, так как Робот либо разобьется, либо остановится в другой клетке.

Ответ: 1

Прототип Чертежник — как решать?

Последний прототип, который составители включили в 12 задание ЕГЭ по информатике — это Чертежник. Здесь при решении важно правильно составить систему уравнений и найти наибольший/наименьший делитель двух чисел. Посмотрим, как это сделать.

Пример 4 (Чертежник)

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b).

Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, −3) переместит Чертёжника в точку (6, −1).

Цикл

означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).

Чертёжнику был дан для исполнения следующий алгоритм (количество повторений и величины смещения в первой из повторяемых команд неизвестны):

В результате выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ … РАЗ»?

Решение

Чтобы решить это задание, необходимо обозначить неизвестными пропуски в алгоритме.

Далее составим систему уравнений. Нам известно, как перемещался Чертежник, и сказано, что он вернулся в начальную точку. Получается, его перемещение равно 0.

Теперь мы можем найти n — наибольшее количество повторений цикла. Число n должно быть делителем как 24, так и 16, то есть нам нужно найти НОД(24, 16). Он равен 8. Это и будет ответом к заданию.

Ответ: 8

Что нужно запомнить?

Теперь вы знаете, как решать 12 задание ЕГЭ по информатике! Обязательно прочитайте наш гайд по этому экзамену, если хотите разобраться с остальными темами и заданиями. Там вы найдете структуру экзамена, актуальные прототипы, тематические блоки и лайфхаки от наших преподавателей. Желаем удачи в подготовке 🙂

Источник

Какое максимально возможное количество единиц может находиться в строке после применения

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

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды

преобразует строку 05111150 в строку 0527150.

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

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

исполнителя при этом не изменяется.

выполняется, пока условие истинно.

выполняется команда1 (если условие истинно).

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

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

Известно, что исходная строка содержала более 100 единиц и не содержала других цифр. Укажите минимально возможную длину исходной строки, при которой в результате работы этой программы получится строка, содержащая максимально возможное количество единиц.

Предположим, что исходная строка содержит 101 единицу.

Данный алгоритм сначала заменит шесть первых единиц на четыре двойки, после чего первые три двойки заменятся на две единицы. Затем ещё три единицы, следующие после оставшейся двойки, заменятся на две двойки, после чего три двойки заменятся на две единицы, и останется строка из 96 единиц. То есть, каждую такую итерацию из строки убираются 5 единиц.

Далее алгоритм 18 раз уберёт из строки по 5 единиц и останется строка из шести единиц. После этого первые два раза произойдёт замена трёх единиц на две двойки, а затем первые три двойки заменятся на две единицы и останется строка «112». Всего 2 единицы.

Если в исходной строке будет 102 единицы, то после работы алгоритма останется строка «1121». Если в исходной строке будет 103 единицы, то после работы алгоритма останется строка «11211». Если в исходной строке будет 104 единицы, то после работы алгоритма останется строка «221», значит, ответ — 103.

Приведём код программы для решения данной задачи на Python:

while (‘111’ in strng):

strng = strng.replace(‘111′, ’22’, 1)

strng = strng.replace(‘222′, ’11’, 1)

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

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды

преобразует строку 05111150 в строку 0527150.

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

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

исполнителя при этом не изменяется.

выполняется, пока условие истинно.

выполняется команда1 (если условие истинно).

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

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

ПОКА нашлось (01) ИЛИ нашлось (02) ИЛИ нашлось (03)

Известно, что исходная строка начиналась с нуля, а далее содержала только единицы, двойки и тройки. После выполнения данной программы получилась строка, содержащая 15 единиц, 10 двоек и 60 троек. Сколько единиц было в исходной строке?

Заметим, что порядок цифр в исходной строке не важен. Из строки «01» получается строка «30». Строка «02» сначала преобразуется в строку «101», а затем получается строка «130». Строка «03» сначала преобразуется в строку «202», затем преобразуется в строку «2101», после чего получается строка «2130».

Заметим, что после преобразования исходной строки получилась строка, содержащая 10 двоек. Значит, в исходной строке должно содержаться 10 троек, поскольку только строка «03» после всех преобразований в получившейся подстроке содержит двойку. Таким образом, если исходная строка начинается с нуля, а далее содержит 10 троек, то получившаяся строка будет содержать 10 двоек, 10 единиц и 10 троек.

Поскольку строка после выполнения также должна содержать 15 единиц, в исходной строке, помимо 10 троек, должно содержаться ещё 5 двоек, поскольку строка «02» преобразуется в строку «130».

Тогда, чтобы получившаяся строка содержала 60 троек, она также должна содержать ещё 45 единиц, поскольку строка «01» преобразуется в строку «30».

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

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды

преобразует строку 05111150 в строку 0527150.

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

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

исполнителя при этом не изменяется.

выполняется, пока условие истинно.

выполняется команда1 (если условие истинно).

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

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

ПОКА нашлось (01) ИЛИ нашлось (02) ИЛИ нашлось (03)

Известно, что исходная строка начиналась с нуля, а далее содержала только единицы, двойки и тройки. После выполнения данной программы получилась строка, содержащая 20 единиц, 10 двоек и 70 троек. Сколько единиц было в исходной строке?

Заметим, что порядок цифр в исходной строке не важен. Из строки «01» получается строка «30». Строка «02» сначала преобразуется в строку «101», а затем получается строка «130». Строка «03» сначала преобразуется в строку «202», затем преобразуется в строку «2101», после чего получается строка «2130».

Заметим, что после преобразования исходной строки получилась строка, содержащая 10 двоек. Значит, в исходной строке должно содержаться 10 троек, поскольку только строка «03» после всех преобразований в получившейся подстроке содержит двойку. Таким образом, если исходная строка начинается с нуля, а далее содержит 10 троек, то получившаяся строка будет содержать 10 двоек, 10 единиц и 10 троек.

Поскольку строка после выполнения также должна содержать 20 единиц, в исходной строке, помимо 10 троек, должно содержаться ещё 10 двоек, поскольку строка «02» преобразуется в строку «130».

Тогда, чтобы получившаяся строка содержала 70 троек, она также должна содержать ещё 50 единиц, поскольку строка «01» преобразуется в строку «30».

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

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды

преобразует строку 05111150 в строку 0527150.

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

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

исполнителя при этом не изменяется.

выполняется, пока условие истинно.

выполняется команда1 (если условие истинно).

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

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

ПОКА нашлось (01) ИЛИ нашлось (02) ИЛИ нашлось (03)

Известно, что исходная строка начиналась с нуля, а далее содержала только единицы, двойки и тройки. После выполнения данной программы получилась строка, содержащая 40 единиц, 10 двоек и 8 троек. Сколько единиц было в исходной строке?

Заметим, что порядок цифр в исходной строке не важен. Из строки «01» сначала получается строка «2302», а потом получается строка «2310». Строка «02» преобразуется в строку «10». Строка «03» сначала преобразуется в строку «201», затем преобразуется в строку «22302», после чего получается строка «22310».

Заметим, что после преобразования исходной строки получилась строка, содержащая 8 троек. Если в исходной строке было 8 единиц, тогда в получившейся строке будет 8 троек и 8 двоек, что не подходит, поскольку двоек должно быть 10. Если в исходной строка было 7 единиц, тогда в получившейся строке будет 7 троек и 7 двоек, этот вариант тоже не подходит, поскольку при добавлении в исходную строку троек в получившейся в результате преобразований строке будет только 9 двоек. Если в исходной строке было 6 единиц, то после преобразования получится шесть единиц, шесть двоек и шесть троек. Далее, добавим к исходной строке две тройки. Тогда после преобразования строки, состоящей из нуля, шести единиц и двух троек получится строка, состоящая из восьми единиц, десяти двоек и восьми троек. Остальные цифры в исходной строке — двойки.

Таким образом, в исходной строке было шесть единиц.

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

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды

преобразует строку 05111150 в строку 0527150.

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

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

исполнителя при этом не изменяется.

выполняется, пока условие истинно.

выполняется команда1 (если условие истинно).

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

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

ПОКА нашлось (01) ИЛИ нашлось (02) ИЛИ нашлось (03)

Известно, что исходная строка начиналась с нуля, а далее содержала только единицы, двойки и тройки. После выполнения данной программы получилась строка, содержащая 50 единиц, 12 двоек и 7 троек. Сколько единиц было в исходной строке?

Заметим, что порядок цифр в исходной строке не важен. Из строки «01» сначала получается строка «2302», а потом получается строка «2310». Строка «02» преобразуется в строку «10». Строка «03» сначала преобразуется в строку «201», затем преобразуется в строку «22302», после чего получается строка «22310».

Заметим, что после преобразования исходной строки получилась строка, содержащая 7 троек. Если в исходной строке было 7 единиц, тогда в получившейся строке будет 7 троек и 7 двоек, что не подходит, поскольку при добавлении в исходную строку троек в получившейся в результате преобразований строке не получить 12 двоек.

Если в исходной строке было 6 единиц, тогда в получившейся строке будет 6 троек и 6 двоек, этот вариант тоже не подходит, поскольку при добавлении в исходную строку троек в получившейся в результате преобразований строке не получить 12 двоек. Похожие ситуации будут, если в исходной строке будет от 3 до 5 единиц.

Если в исходной строке было 2 единицы, то после преобразования получится две единицы, две двойки и две тройки. Далее, добавим к исходной строке две тройки. Тогда после преобразования строки, состоящей из нуля, двух единиц и пяти троек получится строка, состоящая из семи единиц, двенадцати двоек и семи троек. Остальные цифры в исходной строке — двойки.

Таким образом, в исходной строке было две единицы.

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

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды

преобразует строку 05111150 в строку 0527150.

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

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

исполнителя при этом не изменяется.

выполняется, пока условие истинно.

выполняется команда1 (если условие истинно).

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

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

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

Известно, что исходная строка начиналась с нуля и заканчивалась нулём, а между ними содержала только единицы, двойки и тройки. После выполнения данной программы получилась строка, содержащая 23 единицы, 48 двоек и 41 тройку. Сколько цифр было в исходной строке?

Заметим, что порядок цифр между нулями в исходной строке не важен. Из строки «01» получается строка «210». Строка «02» преобразуется в строку «320». Строка «03» сначала преобразуется в строку «3012», затем преобразуется в строку «32102», после чего получается строка «321320».

Заметим, что после преобразования исходной строки получилась строка, содержащая 23 единицы. Если в исходной строке было 23 тройки, тогда в получившейся строке будет 46 троек, что не подходит, поскольку троек должно быть 41. Аналогичная ситуация повторяется, если в исходной строке будет 22 тройки и 21 тройка.

Если в исходной строке было 20 троек, тогда в получившейся строке будет 20 единиц, 40 троек и 40 двоек, этот вариант тоже не подходит, поскольку при добавлении в исходную строку единицы и двоек не получится результата, описанного в условии. Аналогичная ситуация повторяется, если в исходной строке будет 17, 18 или 19 троек.

Если в исходной строке было 16 троек, то после преобразования получится 16 единиц, 32 двойки и 32 тройки. Далее, добавим к исходной строке 7 единиц. Тогда после преобразования строки, состоящей из нуля, 7 единиц и 16 троек получится строка, состоящая из 23 единиц, 39 двоек и 32 троек. Остальные цифры в исходной строке — 9 двоек.

Таким образом, в исходной строке 7 + 9 + 16 + 2 = 34 цифры.

Приведём другое решение.

Заметим, что порядок цифр между нулями в исходной строке не важен. Из строки «01» получается строка «210». Строка «02» преобразуется в строку «320». Строка «03» сначала преобразуется в строку «3012», затем преобразуется в строку «32102», после чего получается строка «321320».

Пусть в исходной строке было x единиц, y двоек и z троек. Тогда в получившейся строке количество единиц будет равно x + z, количество двоек будет равно x + y + 2z и количество троек будет равно y + 2z. Решив получившуюся систему уравнений, найдем x = 7, y = 9; z = 16.

Следовательно, в исходной строке было 7 единиц, 9 двоек, 16 троек и два нуля, всего 7 + 9 + 16 + 2 = 34 цифры.

Источник