Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом:
1. Строится двоичная запись числа N.
2. Подсчитывается количество чётных и нечётных цифр в десятичной записи заданного числа. Если в десятичной записи больше чётных цифр, то в конец двоичной записи
3−4. Пункт 2 повторяется для вновь полученных чисел ещё два раза.
5. Результатом работы алгоритма становится десятичная запись полученного числа R.
Пример. Дано число N = 14. Алгоритм работает следующим образом:
1. Строим двоичную запись: 1410 = 11102.
2. В записи числа 14 чётных и нечётных цифр поровну. Число 14 чётное, дописываем к двоичной
3. В записи числа 28 чётных цифр больше нечётных, дописываем к двоичной
4. В записи числа 57 нечётных цифр больше, дописываем к двоичной
5. Результат работы алгоритма R = 114.
Определите количество принадлежащих отрезку [876 544; 1 234 567 899] чисел, которые могут получиться в результате работы этого алгоритма.
Приведём решение на языке Python.
o1 = 0
o2 = 0
q1 = bin(876544)[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 876544 <= r and r <= 1234567899:
o1 = n
break
k1 = bin(1234567899)[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 876544 <= r and r <= 1234567899:
o2 = n
print(o2 - o1 + 1)
Ответ: 154211420.
Приведём решение Юли Муртазиной на языке Python.
def alg(n):
for u in range (3):
res = [int(x) for a,x in enumerate(str(n))]
sen, sans = 0, 0
for i in res:
if i % 2 == 0:
sen += 1
else:
sans += 1
n = n * 2 + 1 if (sen > sans or (sen == sans and n % 2 == 1)) else n * 2
return n
a,b = 876544, 1234567899
n1 = a // 8-5
while alg(n1) < a:
n1 += 1
n2 = b // 8-5
while alg(n2) <= b:
n2 += 1
print(n2 - n1)