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

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

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

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

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

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

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

 

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

НА­ЧА­ЛО

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

                        за­ме­нить (033, 21120)

                        за­ме­нить (034, 22120)

                        за­ме­нить (04, 220)

                        за­ме­нить (030, 100)

                КОНЕЦ ПОКА

КОНЕЦ

 

Из­вест­но, что в ис­ход­ной стро­ке A было ровно два нуля  — на пер­вом и на по­след­нем месте, а после вы­пол­не­ния дан­ной про­грам­мы по­лу­чи­лась стро­ка B, со­дер­жа­щая 65 цифр, и сумма цифр стро­ки B ока­за­лась про­стым чис­лом. Какое наи­боль­шее ко­ли­че­ство четвёрок могло быть в стро­ке A?

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

Ре­ше­ние.

При­ведём ана­ли­ти­че­ское ре­ше­ние.

Про­ве­рим как ме­ня­ет­ся после пре­об­ра­зо­ва­ние сумма чисел и их ко­ли­че­ство:

033 -> 21120 сумма чисел 6 -> 6 ко­ли­че­ство чисел (без учета 0) 2 -> 4

034 -> 22120 сумма чисел 7 -> 7 ко­ли­че­ство чисел (без учета 0) 2 -> 4

04 -> 220 сумма чисел 4 -> 4 ко­ли­че­ство чисел (без учета 0) 1 -> 2

030 -> 100 стро­ка, после ко­то­рой цикл за­вер­шить­ся.

 

Можно за­ме­тить, что в из­на­чаль­ной стро­ке точно была одна 3, так как цикл за­вер­шить­ся толь­ко по по­след­ней стро­ке. Также сумма цифр на входе будет от­ли­чать­ся от суммы цифр на вы­хо­де на 2, так как одну 3 ме­ня­ем на одну 1. Ко­ли­че­ство цифр на входе будет мень­ше ко­ли­че­ства цифр на вы­хо­де в два раза. Без учета двух нулей и 3 (ко­то­рую за­ме­нят на 1): на вы­хо­де 65 цифр − два 0 − одна 1  =  62 цифры, на входе в два раза мень­ше  — 31 цифра + два 0 + одна 3. На­пи­шем про­грам­му, ко­то­рая счи­та­ет ми­ни­маль­ную вход­ную сумму, ко­то­рое яв­ля­ет­ся про­стым чис­лом, и вер­нем наи­боль­шее ко­ли­че­ство четвёрок.

 

Код на языке Python.

def Div(n):

for i in range(2, int(n**0.5)+1):

if n % i == 0:

return False

return True

 

for i in range(31,0,-1):

summa = (31-i)*3 + i*4 + 1

if Div(summa):

print(i)

break

 

В ре­зуль­та­те ра­бо­ты про­грам­мы по­лу­ча­ем ответ  — 19.

 

Ответ: 19.


Аналоги к заданию № 68245: 68274 Все

Спрятать решение · Прототип задания · Помощь


О про­ек­те · Ре­дак­ция · Пра­во­вая ин­фор­ма­ция · О ре­кла­ме
© Гущин Д. Д., 2011—2026