Задача к ЕГЭ по информатике на тему «исполнитель «редактор»

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

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

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

Дана программа для исполнителя ОРТОЦЕНТР:

$Н АЧА ЛО$

$П ОК А нашлось(10) И ЛИ наш лось(11) ИЛИ нашлось(330)$

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

$Т О заменить(10,1)$

$И НАЧ Е ЕС ЛИ наш лось(11)$

$Т О заменить(11,3)$

$И НАЧ Е ЕС ЛИ наш лось(330)$

$Т О заменить(330,100)$

$К ОН ЕЦ ЕС ЛИ$

$К ОН ЕЦ ПО КА$

$К ОНЕ Ц$

Найдите сумму всех цифр $3$ , стоящих на нечетных позициях (нумерация индексов начинается с нуля), строки, полученной в результате применения приведённой выше программы к строке

$11 ...1100 ...0033 ...33. ◟--◝11◜5-◞◟--◝20◜0-◞◟--◝5◜5-◞$

Решение ручками:

Начнем работу нашего алгоритма. Так как в исходной строке мы нашли $10$ , то заменим $10$ на $1$ .

Получим строку $1 ...1 0...0 3...3 ◟-◝11◜5 ◞ ◟ ◝1◜99 ◞ ◟ ◝5◜5-◞$

На данной итерации цикла строка больше меняться не будет, идем дальше. Вновь встречаем $10$ , можем заметить, что если встречается $10$ , то количество $0$ уменьшается на один, а количество $1$ остается неизменным, тогда можем выполнить это дейстие еще 199 раз, пока у нас не закончатся $0$ .

Получим строку $1◟-.◝..◜1 ◞ 3◟. ◝..◜3 ◞ 115 55$

Так как у нас уже нет комбинаций $10$ , проверяем следующие условия — находим $11$ , меняем $11$ на $3$ .

Получим строку $31◟-.◝..◜1 ◞3◟-.◝..◜3 ◞ 113 55$

Заметим, что после выполнения данного действия количество $1$ уменьшается на два, а количество $3$ увеличивается на единицу (но все появившиеся $3$ ставятся слева). Тогда выполним это действие еще $113∕∕2 = 56$ раз (так как у нас поделилось с остатком, то $1$ останутся в количестве, равном данному остатку), после этого получим:

$3◟-.◝..◜3 ◞ 13◟. ◝.◜.3◞ 57 55$

На этом работа алгоритма завершится, ведь больше нет подходящих подстрок.

Запишем в ответ сумму цифр $3$ , стоящих на нечетных позициях. Сначала определим индексы всех $3$ : [0, 56] и [58, 112]. Теперь среди этих отрезков находим количество нечетных индексов — оно будет равно $56∕∕2 + (112 − 58)∕∕2 = 55$ , тогда общая сумма подходящих нам цифр $3$ равна $3 ⋅55 = 165$ .

Решение прогой:

s = "1" * 115 + "0" * 200 + "3" * 55
while "10" in s or "11" in s or "330" in s:
    if "10" in s:
        s = s.replace("10", "1", 1)
    elif "11" in s:
        s = s.replace("11", "3", 1)
    elif "330" in s:
        s = s.replace("330", "100", 1)
print(sum([int(s[i]) for i in range(len(list(s))) if int(s[i]) == 3 and i % 2 != 0]))

Ответ: 165

Задача к ЕГЭ по информатике на тему «исполнитель «редактор» – известная строка» №5