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

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

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

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

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

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

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

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

 

Цикл

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

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

    КОНЕЦ ПОКА

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

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

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

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

    КОНЕЦ ЕСЛИ

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

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

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

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

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

    КОНЕЦ ЕСЛИ

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

 

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

НА­ЧА­ЛО

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

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

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

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

    КОНЕЦ ПОКА

КОНЕЦ

 

Из­вест­но, что ис­ход­ная стро­ка на­чи­на­лась с нуля и за­кан­чи­ва­лась нулём, а между ними со­дер­жа­ла толь­ко еди­ни­цы, двой­ки и трой­ки. После вы­пол­не­ния дан­ной про­грам­мы по­лу­чи­лась стро­ка, со­дер­жа­щая 23 еди­ни­цы, 48 двоек и 41 трой­ку. Сколь­ко цифр было в ис­ход­ной стро­ке?

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

Ре­ше­ние.

За­ме­тим, что по­ря­док цифр между ну­ля­ми в ис­ход­ной стро­ке не важен. Из стро­ки 01 по­лу­ча­ет­ся стро­ка 210. Стро­ка 02 пре­об­ра­зу­ет­ся в стро­ку 320. Стро­ка 03 сна­ча­ла пре­об­ра­зу­ет­ся в стро­ку 3012, затем пре­об­ра­зу­ет­ся в стро­ку 32102, после чего по­лу­ча­ет­ся стро­ка 321320.

За­ме­тим, что после пре­об­ра­зо­ва­ния ис­ход­ной стро­ки по­лу­чи­лась стро­ка, со­дер­жа­щая 23 еди­ни­цы. Если в ис­ход­ной стро­ке было 23 трой­ки, тогда в по­лу­чив­шей­ся стро­ке будет 46 троек, что не под­хо­дит, по­сколь­ку троек долж­но быть 41. Ана­ло­гич­ная си­ту­а­ция по­вто­ря­ет­ся, если в ис­ход­ной стро­ке будет 22 трой­ки и 21 трой­ка.

Если в ис­ход­ной стро­ке было 20 троек, тогда в по­лу­чив­шей­ся стро­ке будет 20 еди­ниц, 40 троек и 40 двоек, этот ва­ри­ант тоже не под­хо­дит, по­сколь­ку при до­бав­ле­нии в ис­ход­ную стро­ку еди­ни­цы и двоек не по­лу­чит­ся ре­зуль­та­та, опи­сан­но­го в усло­вии. Ана­ло­гич­ная си­ту­а­ция по­вто­ря­ет­ся, если в ис­ход­ной стро­ке будет 17, 18 или 19 троек.

Если в ис­ход­ной стро­ке было 16 троек, то после пре­об­ра­зо­ва­ния по­лу­чит­ся 16 еди­ниц, 32 двой­ки и 32 трой­ки. Далее, до­ба­вим к ис­ход­ной стро­ке 7 еди­ниц. Тогда после пре­об­ра­зо­ва­ния стро­ки, со­сто­я­щей из нуля, 7 еди­ниц и 16 троек по­лу­чит­ся стро­ка, со­сто­я­щая из 23 еди­ниц, 39 двоек и 32 троек. Осталь­ные цифры в ис­ход­ной стро­ке  — 9 двоек.

Таким об­ра­зом, в ис­ход­ной стро­ке 7 + 9 + 16 + 2  =  34 цифры.

 

При­ведём дру­гое ре­ше­ние.

За­ме­тим, что по­ря­док цифр между ну­ля­ми в ис­ход­ной стро­ке не важен. Из стро­ки 01 по­лу­ча­ет­ся стро­ка 210. Стро­ка 02 пре­об­ра­зу­ет­ся в стро­ку 320. Стро­ка 03 сна­ча­ла пре­об­ра­зу­ет­ся в стро­ку 3012, затем пре­об­ра­зу­ет­ся в стро­ку 32102, после чего по­лу­ча­ет­ся стро­ка 321320.

Пусть в ис­ход­ной стро­ке было x еди­ниц, y двоек и z троек. Тогда в по­лу­чив­шей­ся стро­ке ко­ли­че­ство еди­ниц будет равно x + z, ко­ли­че­ство двоек будет равно x + y + 2z и ко­ли­че­ство троек будет равно y + 2z. Решив по­лу­чив­шу­ю­ся си­сте­му урав­не­ний, най­дем x  =  7, y  =  9; z  =  16.

Сле­до­ва­тель­но, в ис­ход­ной стро­ке было 7 еди­ниц, 9 двоек, 16 троек и два нуля, всего 7 + 9 + 16 + 2  =  34 цифры.

 

Ответ: 34.

 

При­ведём дру­гое ре­ше­ние на языке Python.

for a in range(1, 50):

for b in range(1, 50):

for c in range(1, 50):

string = '0' + a * '1' + b * '2' + c * '3' + '0'

while '00' not in string:

string = string.replace('01', '210', 1)

string = string.replace('02', '320', 1)

string = string.replace('03', '3012', 1)

if string.count('1') == 23 and string.count('2') == 48 and string.count('3') == 41:

print(a + b + c + 2)


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

Раздел кодификатора ФИПИ: 1.6.2 Вы­чис­ли­мость. Эк­ви­ва­лент­ность ал­го­рит­ми­че­ских мо­де­лей