5 номер. Преобразование записей чисел
Алгоритм обработки числа
(М. Шагитов) Входным параметром алгоритма является натуральное число N. На основании этого числа алгоритм строит новое число R, следующим образом:
1. Строится восьмеричная запись числа N.
2. Затем эту запись обрабатывают по следующим правилам:
а) Если число N делится на 7, к записи добавляются две последние цифры в восьмеричной системе.
б) Если число N на 7 не делится, остаток от деления умножается на 7, переводится в восьмеричную систему и добавляется к концу числа.
3. Получившаяся запись представляет собой восьмеричное представление искомого числа R.
Результат переводится в десятичную систему и выводится на экран.
Для иллюстрации, если исходное число равно 16, которое в восьмеричной системе равно 20, результатом будет число 2016 в восьмеричной системе, или 1038 в десятичной. Если исходное число равно 5 (5 в восьмеричной системе), результатом будет число 543 в восьмеричной системе, или 355 в десятичной.
Установите количество чисел R, которые меньше 3000, и могут быть получены путем обработки числа N.
Подсказка
Сначала выполните все шаги для одного N, сохраняя строку после каждого изменения. Затем уточните, что требуется выбрать: N, R или количество значений.
Решение
Разделите решение на два действия: для одного входного числа точно воспроизведите алгоритм, затем отберите результаты по условию задачи. Храните запись числа строкой; основание используемой системы счисления — 10.
Для подсчёта проверьте все входы из заданного диапазона. Если спрашивается количество различных результатов, используйте множество R; если количество исходных чисел — считайте подходящие N, даже когда несколько входов дают один результат.
Строгое «больше» означает >, а «не меньше» — >=; аналогично различайте верхние границы. Диапазон перебора определяйте из ограничений и изменения длины записи, а не произвольной константой. Пример из условия помогает проверить отдельный проход алгоритма.
Ответ: 93.