5 номер. Преобразование записей чисел
Алгоритм обработки числа
(С. Якунин) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1. Строится шестнадцатеричная запись числа.
2. Далее, эта запись обрабатывается по следующему правилу:
а) Если цифр B в ней чётное количество, то к этой записи слева дописывается 1.
б) Если цифр B в ней нечётное количество, то к этой записи справа дописывается 1.
Полученная таким образом запись является шестнадцатеричной записью искомого числа R.
Например, возьмём число 91. Строим шестнадцатеричную запись числа: 5B. Цифра B в нём одна – нечётное количество, значит, единицу дописываем справа. Итоговое число 5B1 переводим в десятичную систему – 1457. Число 1457 и является результатом работы алгоритма.
Определите количество натуральных чисел N, для которых результатом выполнения алгоритма может стать двухзначное число.
Подсказка
Сначала выполните все шаги для одного N, сохраняя строку после каждого изменения. Затем уточните, что требуется выбрать: N, R или количество значений.
Решение
Искомая величина: Определите количество натуральных чисел N, для которых результатом выполнения алгоритма может стать двухзначное число.
Разделите решение на два действия: для одного входного числа точно воспроизведите алгоритм, затем отберите результаты по условию задачи. Храните запись числа строкой; основание используемой системы счисления — 10.
Дописывание справа реализуется как s + suffix, слева — как prefix + s. Добавляйте ровно указанную последовательность символов, включая нули. Числовое сложение вместо соединения строк здесь меняет алгоритм.
Для подсчёта проверьте все входы из заданного диапазона. Если спрашивается количество различных результатов, используйте множество R; если количество исходных чисел — считайте подходящие N, даже когда несколько входов дают один результат.
Строгое «больше» означает >, а «не меньше» — >=; аналогично различайте верхние границы. Диапазон перебора определяйте из ограничений и изменения длины записи, а не произвольной константой. Пример из условия помогает проверить отдельный проход алгоритма.
Ответ: 14.