РЕШУ ЕГЭ — информатика

Задания

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

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

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

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

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

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

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

Цикл

    ПОКА условие

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

    КОНЕЦ ПОКА

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

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

    ЕСЛИ условие

        ТО команда1

    КОНЕЦ ЕСЛИ

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

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

    ЕСЛИ условие

        ТО команда1

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

    КОНЕЦ ЕСЛИ

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

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

НАЧАЛО

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

    заменить (12, 4)

КОНЕЦ ПОКА

КОНЕЦ

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

Решение. Если в строке из десяти единиц и одной двойки алгоритм найдёт и заменит подстроку 12, то сумма всех цифр получившейся строки будет равна 13. Если в строке из десяти единиц и двух двоек алгоритм найдёт и заменит подстроку 12 два раза, то сумма всех цифр получившейся строки будет равна 16. Значит, если в строке будет только пять двоек и алгоритм найдёт и заменит подстроку 12 пять раз, сумма цифр в получившейся строке будет равна 25.

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

При этом все двойки должны чередоваться с единицами, то есть исходная строка может выглядеть, например, так:

121212121211111.

В результате выполнения программы получим строку 4444411111.

Ответ: 5.

Приведём решение Евгений Кузьминовой на Python:

for i in range(1, 10000):

s0 = i*'12' + (10-i)*'1'

s = s0

while '12' in s:

s = s.replace('12', '4', 1)

r = s.count('1') + s.count('2')*2 + s.count('4')*4

if r == 25:

print(s0.count('2'))

break

Приведём решение Михаила Глинский на Python:

s25 = 0

a = 0

while s25 != 25:

a += 1

s = '1'*10 + a*'2'

while '12' in s :

s=s.replace('12','',1)

s=s +'4'

s25 = s.count('1')+s.count('2')*2+s.count('4')*4

print(a)

Приведём решение Бориса Савельева на Python:

from random import shuffle

p = []

for x in range(50):

for i in range (0,1000):

a = list('1'*10 + '2'*x)

shuffle(a)

a = ''.join(a)

while '12' in a:

a = a.replace('12','4',1)

if (a.count('1')*1+a.count('2')*2+a.count('4')*4)==25:

p.append(x)

print(min(p))

№ п/п	№ задания	Ответ
1	27383	5

Ключ