Задания
Версия для печати и копирования в MS Word
Тип 12 № 76227
i

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

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

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

на­шлось (v)

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

 

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

НА­ЧА­ЛО

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

                        за­ме­нить (01, 1023)

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

                        за­ме­нить (03, 102)

                КОНЕЦ ПОКА

КОНЕЦ

 

Из­вест­но, что ис­ход­ная стро­ка на­чи­на­лась с нуля и за­кан­чи­ва­лась нулём, а между ними были толь­ко цифры 1, 2 и 3. После вы­пол­не­ния дан­ной про­грам­мы по­лу­чи­лась стро­ка, со­дер­жа­щая 96 еди­ниц, 0 двоек и 75 троек. Вы­ве­ди­те ми­ни­маль­ную длину ис­ход­ной стро­ки.

Спрятать решение

Ре­ше­ние.

Ко­ли­че­ство сим­во­лов до ра­бо­ты Ре­дак­то­ра:

X01 + X02 + X03 + 2  =  S0,

где X01  — ко­ли­че­ство еди­ниц, X02  — ко­ли­че­ство двоек, X03  — ко­ли­че­ство троек.

Когда, ре­дак­тор начнёт свою ра­бо­ту: X1 + X3 + 2  =  S  — ко­ли­че­ство сим­во­лов после ра­бо­ты Ре­дак­то­ра.

По усло­вию за­да­чи X2  =  0.

Рас­смот­рим це­поч­ки дей­ствий Ре­дак­то­ра и как они вли­я­ют на ко­неч­ное кол-во (еди­ниц и троек). По­нят­но, что двой­ки в этом ал­го­рит­ме убы­ва­ют.

Це­поч­ки для еди­ниц:

1)  01–1023–13103–131102–1311310 (ко­ли­че­ство еди­ниц после по­па­да­ния на 01  — 4, после пол­но­го фор­ма­та стро­ки 4 · X01),

2)  02–310 (ко­ли­че­ство еди­ниц после по­па­да­ния на 02  — 1, после пол­но­го фор­ма­та стро­ки X02),

3)  03–102–1310 (ко­ли­че­ство еди­ниц после по­па­да­ния на 03  — 2, после пол­но­го фор­ма­та стро­ки 2 · X03).

За­пи­шем свя­зу­ю­щее урав­не­ние X1, с на­чаль­ным ко­ли­че­ством (еди­ниц, двоек, троек):

4 · X01 + X02 + 2 · X03  =  X1,

где X1  =  96 по усло­вию за­да­чи.

Це­поч­ки для троек:

1)  01–1023–13103–131102–1311310 (ко­ли­че­ство троек после по­па­да­ния на 01  — 2, после пол­но­го фор­ма­та стро­ки 2 · X01),

2)  02–310 (ко­ли­че­ство троек после по­па­да­ния на 02  — 1, после пол­но­го фор­ма­та стро­ки X02),

3)  03–102–1310 (ко­ли­че­ство троек после по­па­да­ния на 03  — 1, после пол­но­го фор­ма­та стро­ки X03).

За­пи­шем свя­зу­ю­щее урав­не­ние X3, с на­чаль­ным ко­ли­че­ством (еди­ниц, двоек, троек):

2 · X01 + X02 + X03  =  X3,

где X3  =  75  — по усло­вию за­да­чи.

Най­дем ми­ни­маль­ную длину ис­ход­ной стро­ки с по­мо­щью про­грамм­но­го кода на языке Python:

# Поиск ми­ни­маль­но­го S0, пе­ре­бо­ром пе­ре­мен­ных X01, X02, X03

S0 = 10**6

for X01 in range(1, 200):

for X02 in range(1, 200):

for X03 in range(1, 200):

if (f:= (4*X01 + X02 + 2*X03 == 96 and 2*X01 + X02 + X03 == 75)):

S0 = min(S0, X01 + X02 + X03 + 2) # +2, т.к учи­ты­ва­ем два нуля в стро­ке

print(S0)

 

Ответ: 67.

Источник: Проб­ный ЕГЭ Санкт-Пе­тер­бург, 20.02.2025. Ва­ри­ант 2