ID задания: BBA0BB
На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи записываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите такое наименьшее число N, для которого результат работы алгоритма больше 105. В ответе это число запишите в десятичной системе счисления.
Заметим, что после дописывания остатка от деления суммы на два, сумма единиц в двоичном представлении (она же и будет общей суммой) либо останется четной, либо станет ей.
Это значит, что при повторении *дописывания* допишется ‘0’
\(105~=~110~1001_2\)
Тогда ближайшее число большее вышеуказанного, удовлетворяющее условию, будет \(1101010_2\)
Нетрудно проверить, что числа меньше \(1101010_2\) не подходят, так как \(106~=~110~1010_2\).
В этом числе сумма цифр (без учета последних двух) = 3, значит так как \(3~\%~2~=~1\), то предпоследняя цифра должна быть 1, что удовлетворяет. *Отбрасываем* последние 2 бита - получаем \(11010_2 =~26\)
Решение программой:
| python | pascal |
| for n in range(1,100): n2 = bin(n)[2:] if n2.count('1') % 2 == 0: n2 += '0' else: n2 += '1' if n2.count('1') % 2 == 0: n2 += '0' else: n2 += '1' r = int(n2,2) if r > 105: print(n) break | uses school; begin foreach var n in range(1,100) do begin var s := n.tostring.Tobase(2); s := s + (s.CountOf('1') mod 2).ToString; s := s + (s.CountOf('1') mod 2).ToString; var res := dec(s,2); if res > 105 then writeln(n); end; end.
|