Исполнитель «Редактор» – прочие прототипы —Каталог задач по ЕГЭ - Информатика БУ

Ошибка.
Попробуйте повторить позже

Задача 1#11481

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

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

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

заменить (111, 27)

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

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

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

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

Цикл

ПОКА условие

последовательность команд

КОНЕЦ ПОКА

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

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

ПОКА нашлось(СОН) или нашлось(ПОН)

ЕСЛИ нашлось(С)

заменить(С, П)

ИНАЧЕ

заменить(ПОН, КЛОН)

КОНЕЦ ПОКА

КОНЕЦ

Какая строка получится в результате применения приведённой выше программы к строке, состоящей из 9 идущих подряд слов ПОСОН? В ответе запишите полученную строку.

Показать ответ и решение

Благодаря первому условию все С заменяться на П и мы получим строку, состоящую из 9 идущих подряд слов ПОПОН.

После каждое слово ПОН будет заменено на КЛОН. Значит мы получим 9 слов ПОКЛОН.

Значит ответ — ПОКЛОНПОКЛОНПОКЛОНПОКЛОНПОКЛОНПОКЛОНПОКЛОНПОКЛОНПОКЛОН.

Ответ: ПОКЛОНПОКЛОНПОКЛОНПОКЛОНПОКЛОНПОКЛОНПОКЛОНПОКЛОНПОКЛОН

Ошибка.
Попробуйте повторить позже

Задача 2#11498

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

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

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

заменить (111, 27)

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

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

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

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

Цикл

ПОКА условие

последовательность команд

КОНЕЦ ПОКА

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

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

НАЧАЛО

ПОКА нашлось (444)

заменить (444, 33)

заменить (33, 44)

КОНЕЦ ПОКА

КОНЕЦ

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

Показать ответ и решение

Две замены в цикле преобразуют 444 в 44 (убирает одну четвёрку) пока в строке есть 444.

Так как преобразование убирает одну четверку, не имеет значения длина исходной строки (большая 100), ведь получится в результате одна и та же строка — 44.

Тогда нам ничего не мешает взять наименьшее число большее 100. Это 101.

Ответ: 101

Ошибка.
Попробуйте повторить позже

Задача 3#11500

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

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

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

$заменить (111,27)$

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

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

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

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

Цикл

$П ОК А усл овие$

$посл едовательность ком анд$

$К ОН ЕЦ ПО КА$

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

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

$Н АЧА ЛО$

$П ОК А нашлось (4444)$

$зам енить (444,333)$

$зам енить (33,44)$

$К ОН ЕЦ ПО КА$

$К ОНЕ Ц$

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

Показать ответ и решение

Изначально не совсем понятно как конечное количество четвёрок зависит от начального. Попробуем проделать вручную операции над несколькими строками. Пусть $n$ — начальное количество четверок.

1) $n = 10$ : $4444444444 → 4434444444 → 4444334444 → 4434334444 → 4434443334.$ Получили $6$ четверок

2) $n = 11$ : $44444444444 → 44344444444 → 44443344444 → 44343344444 → 44344433344.$ Получили $7$ четверок.

3) $n = 12$ : $444444444444 → 443444444444 → 444433444444 → 443433444444 → 443444333444.$ Получили $8$ четверок.

Теперь если мы возьмём $n = 13$ , то получим $4434443333334$ , что очень похоже на случай с $n = 10$ и при этом в строке снова $6$ четверок.

Мы получили закономерность, дальше количество четвёрок будет повторяться $(6,7,8)$ .

Значит нам нужно получить $6$ четверок в конце. Это возможно только при $n$ таком, что его остаток от деления на $3$ равен $1$ .

Минимальное такое число, большее $100$ — $103$ .

naim = 10 ** 10
ans = 0
for i in range(101, 1000):
    s = ’4’ * i
    while ’4444’ in s:
        s = s.replace(’444’, ’333’, 1)
        s = s.replace(’33’, ’44’, 1)
    if s.count(’4’) % 2 == 0 and s.count(’4’) < naim:
        ans = i
        naim = s.count(’4’)
print(ans)

Ответ: 103

Ошибка.
Попробуйте повторить позже

Задача 4#11504

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

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

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

заменить (111, 27)

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

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

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

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

Цикл

ПОКА условие

последовательность команд

КОНЕЦ ПОКА

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

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

НАЧАЛО

ПОКА нашлось(LL)

заменить(BU, LL)

ЕСЛИ НЕ нашлось(BULL)

заменить(LLLLLL, CAT)

КОНЕЦ ПОКА

КОНЕЦ

Алгоритм выше превращает быков (BULL) в милых котиков (CAT). При этом котики боятся быков, поэтому пока есть хотя бы один бык котик появляться не будет. Сколько раз алгоритм сделает команду заменить, если в итоге должно получиться ровно два котика?

Показать ответ и решение

Алгоритм заменяет все строки BULL на LLLL. Также должно было появится два котика (из двух строк LLLLLL). Значит дожно было получится в промежуточном результате 12 символов L. Это возможно если изначально в строке было три BULL.

Произойдет три замены BU на LL и две замены LLLLLL на CAT. В итоге программа сделает 5 замен.

Ответ: 5

Ошибка.
Попробуйте повторить позже

Задача 5#30122

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

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

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

$заменить (111,27)$

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

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

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

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

Цикл

$П ОК А усл овие$

$посл едовательность ком анд$

$К ОН ЕЦ ПО КА$

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

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

$Н АЧА ЛО$

$П ОК А нашлось(AB )$

$зам енить(A, BB )$

$зам енить(B, CCC )$

$зам енить(CCCCC, AB )$

$зам енить(DC, DDF )$

$зам енить(DF, E)$

$К ОН ЕЦ ПО КА$

$К ОНЕ Ц$

Сколько раз встретится буква $E$ в строке, полученной после выполнения алгоритма выше для строки состоящей из последовательности букв $ABCDF$ повторяющейся $60$ раз? В ответ укажите только число.

Показать ответ и решение

Для решения этого задания напишем программу:

# Создаем исходную строку
s = ’ABCDF’ * 60
# Аналог пока нашлось(AB)
while ’AB’ in s:
    # Проводим замену по одному разу
    s = s.replace(’A’, ’BB’, 1)
    s = s.replace(’B’, ’CCC’, 1)
    s = s.replace(’CCCCC’, ’AB’, 1)
    s = s.replace(’DC’, ’DDF’, 1)
    s = s.replace(’DF’, ’E’, 1)
print(s.count(’E’)) # Вывод количества символов E в строке

Ответ: 60

Ошибка.
Попробуйте повторить позже

Задача 6#30123

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

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

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

заменить (111, 27)

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

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

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

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

Цикл

ПОКА условие

последовательность команд

КОНЕЦ ПОКА

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

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

НАЧАЛО

ПОКА нашлось(LL)

заменить(BU, LL)

ЕСЛИ НЕ нашлось(BULL)

заменить(LLLLLL, CAT)

КОНЕЦ ПОКА

КОНЕЦ

Алгоритм выше превращает быков (BULL) в милых котиков (CAT). При этом котики боятся быков, поэтому пока есть хотя бы один бык котик появляться не будет. Сколько раз алгоритм сделает команду заменить, если в итоге должно получиться ровно два котика?

Примечание: входная строка должна состоять только из быков.

Показать ответ и решение

Алгоритм заменяет все строки BULL на LLLL. Также должно было появится два котика (из двух строк LLLLLL). Значит дожно было получится в промежуточном результате 12 символов L. Это возможно если изначально в строке было три BULL.

Произойдет три замены BU на LL и две замены LLLLLL на CAT. В итоге программа сделает 5 замен.

Решение программой

for i in range(1, 100):
    a = "BULL" * i
    ans = 0
    flag = False  # Чтобы найти самый первый
    while "LL" in a:
        if "BU" in a:  # Если выполнится замена
            a = a.replace("BU", "LL", 1)
            ans += 1
        if not ("BULL" in a):
            a = a.replace("LLLLLL", "CAT", 1)
            ans += 1
        if a.count("L") == len(a) or ans > 1000:  # Бесконечный цикл, если будут одни L
            break
    if a.count("CAT") == 2:
        print(ans)
        break

Ответ: 5

Ошибка.
Попробуйте повторить позже

Задача 7#63513

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

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

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

Например, выполнение команды заменить(111, 27) преобразует строку 05111150 в строку 0527150.

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

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

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

Цикл

ПОКА *условие*

*последовательность команд*

КОНЕЦ ПОКА

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

В конструкции

ЕСЛИ *условие*

ТО *команда 1*

ИНАЧЕ *команда 2*

КОНЕЦ ЕСЛИ

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

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

НАЧАЛО

ПОКА нашлось (>0) ИЛИ нашлось (>1) ИЛИ нашлось (>2)

ЕСЛИ нашлось (>0)

ТО заменить (>0, 22>)

КОНЕЦ ЕСЛИ

ЕСЛИ нашлось (>1)

ТО заменить (>1, 2>)

КОНЕЦ ЕСЛИ

ЕСЛИ нашлось (>2)

ТО заменить (>2, 1>)

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

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

Показать ответ и решение

Решение 1

Рассмотрим переходы цифр:

$0 → 22$
$1 → 2$
$2 → 1$

Получаем, что каждый ноль это $+4$ в сумму, каждая единица $+2$ , каждая двойка $+ 1$ . Посчитаем пока что, какая будет сумма после обработки двоек и нулей. $S = 15⋅4 + 1⋅15 = 75$ , ближайшее простое число это $79$ , нам не хватает $4$ до такой суммы. Каждая единица это $+ 2$ , значит, чтобы получить $+ 4$ нам нужно две единицы.

Решение 2

def is_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return n > 1

for n in range(0, 100):
    s = ’>’ + ’0’ * 15 + ’1’ * n + ’2’ * 15
    while ’>0’ in s or ’>1’ in s or ’>2’ in s:
        if ’>0’ in s:
            s = s.replace(’>0’, ’22>’)
        if ’>1’ in s:
            s = s.replace(’>1’, ’2>’)
        if ’>2’ in s:
            s = s.replace(’>2’, ’1>’)
    summa = 0
    for i in s[0:-1]:
        summa += int(i)
    if is_prime(summa):
        print(n)
        break

Ответ: 2

Ошибка.
Попробуйте повторить позже

Задача 8#63514

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

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

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

Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.

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

НАЧАЛО

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

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

заменить (11, 2)

заменить (012, 30)

заменить (010, 00)

КОНЕЦ ПОКА

КОНЕЦ

Известно, что исходная строка содержала ровно два нуля – на первом и на последнем месте, 50 двоек, больше 100 единиц и не содержала других цифр. После выполнения программы получилась строка, сумма цифр которой оказалась простым числом. Какое наименьшее количество единиц могло быть в исходной строке?

Показать ответ и решение

Решение 1

Распишем все переходы для пар из единиц и двоек.

$011 → 02 → 101$
$012 → 30$
$021 → 1011 → 102 → 1101$
$022 → 1012 → 130$

Задача у нас про сумму цифр, как видим сумма при переходе пар константна.

Рассмотрим переходы одиночных цифр между нулями.

$010 → 00$
$020 → 1010 → 100$

Как видим, сумма оба раза уменьшилась на единицу. Получается, что если изначальная сумма была $s$ , то сумма после работы алгоритма будет $s − 1$ , однако если не допустить этих оперпций, то сумма не изменится и так потребуется меньшее количество единиц. Это можно сделать поставив после нуля 25 двоек, затем все единицы, и снова 25 двоек. Начальная сумма цифр $50⋅2+ 1 ⋅100 = 200$ . Нам необходимо количество единиц $> 100$ . Минимальное простое число большее $200$ — это $211$ , получаем $111$ — количество единиц.

Решение 2

def is_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return n > 1

for n in range(101, 1000):
    s = "0" + ’2’ * 25 + ’1’ * n + ’2’ * 25 + ’0’
    while not (’00’ in s):
        s = s.replace(’02’, ’101’, 1)\
            .replace(’11’, ’2’, 1)\
            .replace(’012’, ’30’, 1)\
            .replace(’010’, ’00’, 1)
    if is_prime(sum(int(x) for x in s)):
        print(n)
        break

Ответ: 111

Ошибка.
Попробуйте повторить позже

Задача 9#63831

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

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

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

Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Дана программа для исполнителя Редактор:

НАЧАЛО

ПОКА нашлось (111)

заменить (111, 22)

заменить (222, 11)

КОНЕЦ ПОКА

КОНЕЦ

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

Показать ответ и решение

mndl = 10000
mn = 10000
for i in range(51, 1000):
    s = ’1’*i
    while ’111’ in s:
        s = s.replace(’111’, ’22’, 1)
        s = s.replace(’222’, ’11’, 1)
    if s.count(’1’) < mndl:
        mndl = s.count(’1’)
        mn = i
print(mn)

Ответ: 54

Ошибка.
Попробуйте повторить позже

Задача 10#64060

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. На выполнение Редактору дана следующая программа:

ПОКА нашлось(55555) ИЛИ нашлось(33333)

ЕСЛИ нашлось(55555)

ТО заменить(55555, 333)

ИНАЧЕ заменить(33333,555)

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

На вход программе подана строка из 1024 подряд идущих символов 5. Сколько замен произойдет в ходе работы алгоритма?

Показать ответ и решение

s=’5’*1024
k=0
while ’55555’ in s or ’33333’ in s:
    if ’55555’ in s:
        s=s.replace(’55555’, ’333’, 1)
        k+=1
    else:
        s=s.replace(’33333’, ’555’, 1)
        k+=1
print(k)

Ответ: 508

Ошибка.
Попробуйте повторить позже

Задача 11#74227

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

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

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

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

Б) Нашлось ( $v$ ).

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

Цикл

ПОКА условие

Последовательность команд

КОНЕЦ ПОКА

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

В конструкции:

ЕСЛИ условие

команда1

ИНАЧЕ

команда2

КОНЕЦ ЕСЛИ

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

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

НАЧАЛО

ПОКА нашлось (1111) ИЛИ нашлось (444)

ЕСЛИ нашлось (1111)

ТО заменить (1111,41)

ИНАЧЕ заменить (444, 1)

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Известно, что исходная строка состояла из n цифр «1», при этом не содержав других цифр. Укажите минимальное значение n, при котором сумма цифр в строке будет равна количеству замен.

Показать ответ и решение

for n in range(1,1500):
    c = 0
    s = n*’1’
    while ’1111’ in s or ’444’ in s:
        if (’1111’) in s:
            s = s.replace(’1111’,’41’,1)
            c += 1
        else:
            s = s.replace(’444’,’1’,1)
            c += 1
    if c == sum(map(int,s)):
        print(n)
        break

Ответ: 12

12.04 Исполнитель «Редактор» – прочие прототипы