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

Задания

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

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

2.  В конец двоичной записи добавляется двоичный код остатка от деления числа N на 4.

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

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

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

2.  Остаток от деления 13 на 4 равен 1, добавляем к двоичной записи цифру 1, получаем 11011₂  =  27₁₀.

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

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

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

2.  Остаток от деления 14 на 4 равен 2, добавляем к двоичной записи цифры 10 (10₂  =  2₁₀), получаем 111010₂  =  58₁₀.

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

Назовём доступными числа, которые могут получиться в результате работы этого алгоритма. Например, числа 27 и 58  — доступные. Определите количество доступных чисел, принадлежащих отрезку [1 000 000 000; 1 789 456 123].

Решение. Возможные остатки от деления числа на 4  — это: 0, 1, 2, 3.

Рассмотрим, какие цифры будут на конце чисел, при делении на 4 дающие остаток 0, 1, 2 или 3.

Остаток 0 при делении на 4 дадут числа, двоичная запись которых заканчивается на 00, добавляем остаток 0. В результате автомата доступное число будет оканчиваться на 000. Следовании при делении на 8 должен быть остаток 0.

Остаток 1 при делении на 4 дадут числа, двоичная запись которых заканчивается на 01, добавляем остаток 1. В результате автомата доступное число будет оканчиваться на 011. Следовании при делении на 8 должен быть остаток 3.

Остаток 2 при делении на 4 дадут числа, двоичная запись которых заканчивается на 10, добавляем остаток 2 (10 в в двоичной записи). В результате автомата доступное число будет оканчиваться на 1010. Следовании при делении на 16 должен быть остаток 10.

Остаток 3 при делении на 4 дадут числа, двоичная запись которых заканчивается на 11, добавляем остаток 3 (11 в двоичной записи). В результате автомата доступное число будет оканчиваться на 1111. Следовании при делении на 16 должен быть остаток 15.

Посчитаем доступные числа.

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

count = 0

for x in range(1_000_000_000, 1_789_456_123+1):

if x%16 in [10,15] or x%8 in [0,3]:

count += 1

print(count)

Ответ: 296046047.

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

def count_Ns(L, U, mod_value, multiplier, increment):

N_min = (L - increment + multiplier - 1) // multiplier

N_max = (U - increment) // multiplier

while N_min % 4 != mod_value:

N_min += 1

while N_max % 4 != mod_value:

N_max -= 1

if N_min > N_max:

return 0

return ((N_max - N_min) // 4) + 1

L = 1_000_000_000

U = 1_789_456_123

total_count = 0

total_count += count_Ns(L, U, mod_value=0, multiplier=2, increment=0)

total_count += count_Ns(L, U, mod_value=1, multiplier=2, increment=1)

total_count += count_Ns(L, U, mod_value=2, multiplier=4, increment=2)

total_count += count_Ns(L, U, mod_value=3, multiplier=4, increment=3)

print(total_count)

Приведём решение Юрия Красильникова на языке Python.

def количество(от,до,множитель, остаток):

большеравноот=((от-остаток-1)//множитель+1)*множитель+остаток

большеравнодо=((до-остаток-1)//множитель+1)*множитель+остаток

return (большеравнодо-большеравноот)//множитель

print(sum([количество(1000000000,1789456123+1,16,остаток) for остаток in [0,3,8,10,11,15]]))

№ п/п	№ задания	Ответ
1	64890	296046047

Ключ