Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. В конец двоичной записи добавляются две цифры, соответствующие двоичной записи остатка от деления исходного числа
3. В конец двоичной записи числа, полученного на предыдущем шаге, добавляются три цифры, соответствующие двоичной записи остатка от деления этого числа
4. Результатом работы алгоритма становится десятичная запись полученного числа R.
Пример. Дано число N = 13. Алгоритм работает следующим образом:
1. Строим двоичную запись: 1310 = 11012.
2. Остаток от деления 13
3. Остаток от деления 53
4. Результат работы алгоритма R = 427.
Определите количество принадлежащих отрезку [1 111 111 110; 1 444 444 416] чисел, которые могут получиться в результате работы этого алгоритма.
Приведём решение Юрия Красильникова на языке Python.
def f(n):
s2 = bin(n%3)[2:]
r = int(bin(n)[2:]+'0'*(2-len(s2))+s2,2)
s2 = bin(r%5)[2:]
return int(bin(r)[2:]+'0'*(3-len(s2))+s2,2)
a,b = 1111111110,1444444416
n = a//32-5
m = b//32-5
while f(n) < a: n+=1
while f(m) <= b: m+=1
print(m-n)
Ответ: 10416665.
Приведём решение Юрия Красильникова на языке Python.
def f(n):
r = n*4 + n%3
return r*8 + r%5
a,b = 1111111110,1444444416
n = a//32-5
m = b//32-5
while f(n) < a: n+=1
while f(m) <= b: m+=1
print(m-n)
Приведём решение Бориса Савельева на языке Python.
ans=0
for n in range (34_500_000,45_500_000):
s=bin(n)[2:]
if 1_111_111_110 <= int(bin(n)[2:]+'0'*(2-len(bin(n%3)[2:]))+bin(n%3)[2:]+'0'*(3-len(bin(int(s,2)%5)[2:]))+bin(int(s,2)%5)[2:],2) <= 1_444_444_416:
ans += 1
print(ans)
Приведём решение Егора Чернецова на языке Python.
count = 0
for N in range(34722222, 45138889):
a = N % 3
b = (4 * N + a) % 5
R = 32 * N + 8 * a + b
if 1111111110 <= R <= 1444444416:
count += 1
print(count)