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