Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

ЕГЭ, Информатика: 12. Выполнение алгоритмов для исполнителей: исполнитель

21. Задание #298424
Решено верно
Решено неверно
Сообщить о проблеме

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

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

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

Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.

В конструкции
ЕСЛИ условие
ТО команда1
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно).

В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

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

НАЧАЛО
ПОКА нашлось (1111) ИЛИ нашлось (88888)
    ЕСЛИ нашлось (1111)
        ТО заменить (1111, 888)
        ИНАЧЕ заменить (88888, 888)
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Конструкция ЕСЛИ–ИНАЧЕ одна, значит, за проход цикла выполняется ровно одна замена. Приоритет у первой ветки: пока в строке есть $1111$, вторая ветка не работает вовсе.

Первая фаза. Строка из $81$ единицы. Каждый шаг превращает $1111$ в $888$: единиц становится на четыре меньше, восьмёрок на три больше, причём восьмёрки копятся слева, а единицы остаются справа. Так как $81 = 4 \cdot 20 + 1$, замена сработает $20$ раз, после чего останется хвост из одной единицы, а слева накопится $3 \cdot 20 = 60$ восьмёрок. Строка принимает вид из $60$ восьмёрок и одной единицы.

Вторая фаза. Четырёх единиц подряд больше нет, включается вторая ветка: $88888 \to 888$, то есть восьмёрок каждый раз становится на две меньше. Замена возможна, пока восьмёрок не меньше пяти. Убавляем по две от чётного числа $60$: $60, 58, 56, \ldots, 6, 4$. На четырёх восьмёрках цепочка $88888$ уже не находится, и цикл завершается. Это $\frac{60 - 4}{2} = 28$ шагов.

Хвост из одной единицы всё это время не трогается: четыре единицы подряд там взяться неоткуда. Итого остаются $4$ восьмёрки и $1$ единица: $88881$. Всего цикл отработал $20 + 28 = 48$ шагов.

Обратите внимание: ответ определяется остатком от деления $81$ на $4$ (длина хвоста из единиц) и чётностью числа восьмёрок. Здесь $60$ чётно, поэтому процесс упирается ровно в $4$ восьмёрки; если бы восьмёрок было нечётное число, осталось бы $3$.

def run(s):
    while '1111' in s or '88888' in s:
        if '1111' in s:
            s = s.replace('1111', '888', 1)     # только первое вхождение
        else:
            s = s.replace('88888', '888', 1)
    return s

print(run('1' * 81))   # 88881

Проверка на малых значениях подтверждает логику: строка из $8$ единиц даёт $8888$, из $9$ — $88881$, из $12$ — $888$, из $13$ — $8881$.

Показать
Очки опыта 20
Спросить Зави
22. Задание #298423
Решено верно
Решено неверно
Сообщить о проблеме

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

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

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

Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.

В конструкции
ЕСЛИ условие
ТО команда1
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно).

В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Определите количество нулей в строке, получившейся в результате применения приведённой ниже программы к входной строке $\underbrace{100\ldots00}_{55}$, т.е. к строке, состоящей из единицы, за которой следуют $55$ нулей подряд. В ответе запишите только количество нулей в получившейся строке.

НАЧАЛО
ПОКА нашлось (1)
    ЕСЛИ нашлось (10)
        ТО заменить (10, 001)
        ИНАЧЕ заменить (1, 00)
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Единица в строке всё время ровно одна: замена $10 \to 001$ её сохраняет, замена $1 \to 00$ уничтожает, а появиться новой неоткуда. Поэтому достаточно следить за тем, сколько нулей стоит справа от единицы.

Основная ветка. Пока справа от единицы есть хотя бы один нуль, цепочка $10$ находится, и работает замена $10 \to 001$. Что она делает: убирает один нуль справа от единицы и дописывает два нуля слева от неё. Единица как бы сдвигается вправо через строку, оставляя за собой по два нуля вместо одного.

Баланс нулей за такой шаг: $-1$ справа и $+2$ слева, то есть общее количество нулей растёт на $1$.

Сколько таких шагов. Справа от единицы изначально $55$ нулей, и каждый шаг съедает ровно один, поэтому замена $10 \to 001$ сработает $55$ раз. К этому моменту нулей станет $55 + 55 = 110$, а единица окажется последним символом строки.

Завершающий шаг. Теперь цепочки $10$ нет, но единица есть, поэтому срабатывает ветка ИНАЧЕ: $1 \to 00$, что добавляет ещё $2$ нуля. Единиц в строке не остаётся, условие цикла становится ложным, и программа завершается. Всего цикл отработал $56$ шагов.

Итого нулей: $110 + 2 = 112$ (и это вся длина строки, поскольку единицы в ней больше нет).

Общая формула для $k$ нулей на входе: $2k + 2$. Проверка на малых значениях: при $k = 1$ получается $4$, при $k = 2$ — $6$, при $k = 3$ — $8$; при $k = 55$ имеем $2 \cdot 55 + 2 = 112$.

def run(s):
    while '1' in s:
        if '10' in s:
            s = s.replace('10', '001', 1)   # только первое вхождение
        else:
            s = s.replace('1', '00', 1)
    return s

print(run('1' + '0' * 55).count('0'))   # 112
Показать
Очки опыта 20
Спросить Зави
23. Задание #298426
Решено верно
Решено неверно
Сообщить о проблеме

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

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

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

Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.

В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

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

НАЧАЛО
ПОКА нашлось (2222) ИЛИ нашлось (8888)
    ЕСЛИ нашлось (2222)
        ТО заменить (2222, 88)
        ИНАЧЕ заменить (8888, 22)
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Конструкция ЕСЛИ–ИНАЧЕ одна, значит, за проход цикла выполняется ровно одна замена. Приоритет у цепочки $2222$: как только четыре двойки набрались, они тут же схлопываются, и до восьмёрок очередь не доходит.

Проследим за строкой из одних восьмёрок. Пока двоек меньше четырёх, работает ветка ИНАЧЕ: $8888 \to 22$, причём заменяется самое левое вхождение, поэтому двойки копятся в начале строки, а восьмёрки остаются справа сплошным блоком. Двух таких шагов хватает, чтобы получить $2222$ и потерять $8$ восьмёрок. Сразу после этого срабатывает первая ветка: $2222 \to 88$, двойки исчезают полностью, а восьмёрок становится на $2$ больше.

Итого за три шага строка снова состоит из одних восьмёрок, но их стало на $8 - 2 = 6$ меньше. Такой цикл повторяется, пока восьмёрок хватает на две замены, то есть пока их не меньше $8$.

Считаем: $70 = 6 \cdot 11 + 4$, поэтому после $11$ полных циклов ($33$ шага) остаются $4$ восьмёрки.

Разбираем остаток вручную. Строка $8888$: двоек нет, срабатывает $8888 \to 22$, получается $22$. Теперь ни $2222$ (двоек всего две), ни $8888$ в строке нет — условие цикла ложно, программа останавливается. Всего цикл отработал $33 + 1 = 34$ шага.

Ключевой момент — остаток от деления на $6$. Полезно помнить, чем заканчивается дело для остатков $4$, $5$, $6$, $7$: $22$, $228$, $2288$, $22888$ соответственно.

def run(s):
    while '2222' in s or '8888' in s:
        if '2222' in s:
            s = s.replace('2222', '88', 1)   # только первое вхождение
        else:
            s = s.replace('8888', '22', 1)
    return s

print(run('8' * 70))   # 22
Показать
Очки опыта 20
Спросить Зави
24. Задание #298430
Решено верно
Решено неверно
Сообщить о проблеме

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

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

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

Цикл
ПОКА условие 
последовательность команд 
КОНЕЦ ПОКА
выполняется, пока условие истинно.

В конструкции
ЕСЛИ условие
ТО команда1 
ИНАЧЕ команда2 
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

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

НАЧАЛО
ПОКА нашлось (22222) ИЛИ нашлось (9999)
    ЕСЛИ нашлось (22222)
        ТО заменить (22222, 99)
        ИНАЧЕ заменить (9999, 2)
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Конструкция ЕСЛИ–ИНАЧЕ одна, значит, за проход цикла выполняется ровно одна замена. Приоритет у цепочки $22222$: как только пять двоек набралось, они тут же схлопываются, и до девяток очередь не доходит.

Проследим за строкой из одних девяток. Пока двоек меньше пяти, работает ветка ИНАЧЕ: $9999 \to 2$, причём заменяется самое левое вхождение, поэтому двойки копятся в начале строки, а девятки остаются справа сплошным блоком. Пять таких шагов дают $22222$ и уменьшают число девяток на $20$. Сразу после этого срабатывает первая ветка: $22222 \to 99$, двойки исчезают полностью, а девяток становится на $2$ больше.

Итого за шесть шагов строка снова состоит из одних девяток, но их стало на $20 - 2 = 18$ меньше. Такой цикл повторяется, пока девяток хватает на пять замен, то есть пока их не меньше $20$.

Считаем: $99 \to 81 \to 63 \to 45 \to 27 \to 9$. Это пять полных циклов ($30$ шагов), и остаются $9$ девяток.

Разбираем остаток вручную. Из $9$ девяток замена $9999 \to 2$ проходит два раза (съедает $8$ девяток) и даёт строку $229$: две двойки слева и одна девятка справа. Дальше ни $22222$ (двоек всего две), ни $9999$ (девятка одна) в строке нет — условие цикла ложно, программа останавливается. Всего цикл отработал $30 + 2 = 32$ шага.

Обратите внимание: остаток нужно доводить до конца вручную, а не обрывать деление наугад. Например, остаток $20$ дал бы $99$, а остаток $21$ — $999$.

def run(s):
    while '22222' in s or '9999' in s:
        if '22222' in s:
            s = s.replace('22222', '99', 1)   # только первое вхождение
        else:
            s = s.replace('9999', '2', 1)
    return s

print(run('9' * 99))   # 229
Показать
Очки опыта 20
Спросить Зави
25. Задание #298429
Решено верно
Решено неверно
Сообщить о проблеме

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

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

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

Цикл
ПОКА условие 
последовательность команд 
КОНЕЦ ПОКА
выполняется, пока условие истинно.

В конструкции
ЕСЛИ условие
ТО команда1 
ИНАЧЕ команда2 
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

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

НАЧАЛО
ПОКА нашлось (25) ИЛИ нашлось (355) ИЛИ нашлось (555)
    ЕСЛИ нашлось (25)
        ТО заменить (25, 5)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (355)
        ТО заменить (355, 52)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (555)
        ТО заменить (555, 3)
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «$3$», а затем содержащая $n$ цифр «$5$» ($n > 3$). Определите наименьшее значение $n$, при котором в строке, получившейся в результате выполнения программы, останутся только цифры «$5$».

Три оператора ЕСЛИ здесь независимы, а не вложены, поэтому за один проход тела цикла выполняется до трёх замен строго в записанном порядке: сначала $25 \to 5$, затем $355 \to 52$, затем $555 \to 3$, причём каждая работает уже с результатом предыдущей.

Посмотрим на первый проход. Строка $3\underbrace{55\ldots5}{n}$: цепочки $25$ нет; $355 \to 52$ превращает начало в $52$, и остаётся $52\underbrace{55\ldots5}{n-2}$; затем $555 \to 3$ съедает три пятёрки из хвоста. Дальше двойки, тройки и пятёрки начинают перемешиваться: $355 \to 52$ порождает двойки, $25 \to 5$ их уничтожает, $555 \to 3$ снова создаёт тройки.

Поведение оказывается крайне неустойчивым по $n$, никакой простой формулы нет. Достаточно взглянуть на маленькие значения: $n = 6$ даёт $5235$, $n = 7$ — $552$, $n = 8$ — $3$, $n = 9$ — $35$. Поэтому надёжный путь — перебрать значения $n$ подряд и найти первое, при котором в результате нет ни двоек, ни троек.

def run(s):
    while '25' in s or '355' in s or '555' in s:
        if '25' in s:
            s = s.replace('25', '5', 1)      # только первое вхождение
        if '355' in s:
            s = s.replace('355', '52', 1)
        if '555' in s:
            s = s.replace('555', '3', 1)
    return s

n = 4
while set(run('3' + '5' * n)) != {'5'}:
    n += 1
print(n)      # 19

Две типичные ошибки: заменять нужно только первое вхождение (третий аргумент $1$ у replace), и три условия должны проверяться последовательно и независимо — если написать их через elif, ответ изменится.

Перебор даёт первое подходящее значение $n = 19$: программа оставляет строку $55$, состоящую из одних пятёрок. Все меньшие $n$ дают результат, где обязательно есть двойка или тройка ($n = 17$ даёт $352$, $n = 18$ — $52$). Следующие подходящие значения — $23$, $63$, $67$, так что важно брать именно наименьшее.

Показать
Очки опыта 20
Спросить Зави
03:50:00
Решено заданий: 0 из
0 заданий сегодня

Предложить улучшение