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

Задания

Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом:

1.  Строится двоичная запись числа N.

2.  Подсчитывается количество чётных и нечётных цифр в десятичной записи заданного числа. Если в десятичной записи больше чётных цифр, то в конец двоичной записи дописывается 1, если нечётных  — 0. Если чётных и нечётных цифр в десятичной записи поровну, то в конец двоичной записи дописывается 0, если данное число чётное, и 1  — если нечётное.

3−4.  Пункт 2 повторяется для вновь полученных чисел ещё два раза.

5.  Результатом работы алгоритма становится десятичная запись полученного числа R.

Пример. Дано число N  =  14. Алгоритм работает следующим образом:

1.  Строим двоичную запись: 14₁₀  =  1110₂.

2.  В записи числа 14 чётных и нечётных цифр поровну. Число 14 чётное, дописываем к двоичной записи 0, получаем 11100₂  =  28₁₀.

3.  В записи числа 28 чётных цифр больше, дописываем к двоичной записи 1, получаем 111001₂  =  57₁₀.

4.  В записи числа 57 нечётных цифр больше, дописываем к двоичной записи 0, получаем 1110010₂  =  114₁₀.

5.  Результат работы алгоритма R  =  114.

Определите количество принадлежащих отрезку [123 455; 987 654 321] чисел, которые могут получиться в результате работы этого алгоритма.

Решение. Заметим, что указанный алгоритм не меняет порядок чисел. Разделив число 123455 нацело на 2 три раза, получим число 15431. Это минимальное число, из которого при помощи алгоритма может получиться число из требуемого интервала. Но при помощи алгоритма из этого числа получается число 123450. Первое число, из которого получается число, принадлежащее интервалу, это число 15432, результат работы алгоритма 123458. Теперь повторим первую операцию с последним числом интервала, получим число 123456790. Применим к нему алгоритм, результат  — число 987 654 325, следовательно, последнее число, которое нам подходит,  — 123456789, результат работы алгоритма  — 987654316. Таким образом, чисел, из которых может получиться число, попадающее в нужный отрезок, 123456789 − 15431  =  123441358.

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

o1 = 0

o2 = 0

q1 = bin(123455)[2:]

q2 = int(q1[:len(q1)-3], 2)

for n in range(q2 - 10, q2 + 10):

s = bin(n)[2:]

for i in range(3):

count1 = 0

count2 = 0

l = int(s, 2)

l1 = l

while l > 0:

if (l % 10) % 2 == 0:

count2 += 1

l //= 10

elif (l % 10) % 2 != 0:

count1 += 1

l //= 10

if count2 > count1:

s += '1'

elif count2 < count1:

s += '0'

elif count1 == count2:

if l1 % 2 == 0:

s += '0'

else:

s += '1'

r = int(s, 2)

if 123455 <= r and r <= 987654321:

o1 = n

break

k1 = bin(987654321)[2:]

k2 = int(k1[:len(k1) - 3], 2)

for n in range(k2 - 10, k2 + 10):

s = bin(n)[2:]

for i in range(3):

count1 = 0

count2 = 0

l = int(s, 2)

l1 = l

while l > 0:

if (l % 10) % 2 == 0:

count2 += 1

l //= 10

elif (l % 10) % 2 != 0:

count1 += 1

l //= 10

if count2 > count1:

s += '1'

elif count2 < count1:

s += '0'

elif count1 == count2:

if l1 % 2 == 0:

s += '0'

else:

s += '1'

r = int(s, 2)

if 123455 <= r and r <= 987654321:

o2 = n

print(o2 - o1 + 1)

Ответ: 123441358.

Приведём решение Дмитрия Гнутова на языке Python.

def novoech(pr):

for i in range (0, 3):

n = str(pr)

nechet = n.count('1') + n.count('3') + n.count('5') + n.count('7') + n.count('9')

chet = n.count('0') + n.count('2') + n.count('4') + n.count('6') + n.count('8')

if nechet > chet:

pr = pr*2

elif nechet < chet:

pr = pr*2 + 1

elif nechet ==chet:

if nechet%2 == 0:

pr = pr*2

else:

pr = pr*2 + 1

return pr

minch = 123455//8

for pr in range (minch - 1, minch + 2):

r = novoech(pr)

if r >= 123455:

minch = pr

break

maxch = 987654321//8

for pr in range (maxch - 1, maxch + 2):

r = novoech(pr)

if r <= 987654321:

maxch = pr

print ( maxch - minch + 1 )

№ п/п	№ задания	Ответ
1	55592	123441358

Ключ