5 номер. Преобразование записей чисел
Двоичная запись и сумма цифр
На вход алгоритма подаётся натуральное число N меньшее 1000. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если сумма цифр в двоичной записи числа чётная, то к этой записи слева дописывается 10, а иначе – 11;
б) если сумма цифр числа, получившегося в пункте а), в двоичной записи числа нечётная, то к этой записи справа дописывается 11, а иначе – 00.
Полученная таким образом запись является двоичной записью искомого числа R.
Укажите количество чисел R, меньших 860, которые могут быть получены при обработке числа N.
Подсказка
Сначала выполните все шаги для одного N, сохраняя строку после каждого изменения. Затем уточните, что требуется выбрать: N, R или количество значений.
Решение
Искомая величина: Укажите количество чисел R, меньших 860, которые могут быть получены при обработке числа N.
Разделите решение на два действия: для одного входного числа точно воспроизведите алгоритм, затем отберите результаты по условию задачи. Храните запись числа строкой; основание используемой системы счисления — 2.
В двоичной записи сумма цифр равна числу единиц: её удобно получить как s.count("1"). Остаток этой суммы по модулю 2 — бит чётности; он не равен остатку исходного числа по модулю 2. Чётность самого N определяется последним битом.
Дописывание справа реализуется как s + suffix, слева — как prefix + s. Добавляйте ровно указанную последовательность символов, включая нули. Числовое сложение вместо соединения строк здесь меняет алгоритм.
После завершения всех преобразований получите числовой результат: R = int(s, 2). Ограничения на величину R проверяйте численно: лексикографический порядок строк не совпадает с порядком чисел.
Для подсчёта проверьте все входы из заданного диапазона. Если спрашивается количество различных результатов, используйте множество R; если количество исходных чисел — считайте подходящие N, даже когда несколько входов дают один результат.
Строгое «больше» означает >, а «не меньше» — >=; аналогично различайте верхние границы. Диапазон перебора определяйте из ограничений и изменения длины записи, а не произвольной константой. Пример из условия помогает проверить отдельный проход алгоритма.
Ответ: 47.