5 номер. Преобразование записей чисел
Алгоритм обработки числа
На вход алгоритму Галиб-001 подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1) Строится девятиричная запись числа N.
2) Подсчитывается количество пятёрок и семёрок в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается чаще. Если таких цифр несколько, выбирается наибольшая по значению.
3) Шаг 2 повторяется ещё четыре раза.
4) Результат переводится в шестнадцатиричную систему счисления.
При каком наибольшем исходном числе N < 10000 в результате работы алгоритма получится число, которое содержит в себе сочетание BAC?
Подсказка
Сначала выполните все шаги для одного N, сохраняя строку после каждого изменения. Затем уточните, что требуется выбрать: N, R или количество значений.
Решение
Искомая величина: 2) Подсчитывается количество пятёрок и семёрок в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается чаще. Если таких цифр несколько, выбирается наибольшая по значению.
Разделите решение на два действия: для одного входного числа точно воспроизведите алгоритм, затем отберите результаты по условию задачи. Храните запись числа строкой; основание используемой системы счисления — 10.
Повторяемый шаг применяйте последовательно. После первого дописывания сохраните новую строку и только затем вычисляйте следующий добавляемый разряд. Использование исходной суммы на обоих шагах может дать другую запись.
Для подсчёта проверьте все входы из заданного диапазона. Если спрашивается количество различных результатов, используйте множество R; если количество исходных чисел — считайте подходящие N, даже когда несколько входов дают один результат.
Строгое «больше» означает >, а «не меньше» — >=; аналогично различайте верхние границы. Диапазон перебора определяйте из ограничений и изменения длины записи, а не произвольной константой. Пример из условия помогает проверить отдельный проход алгоритма.
Ответ: 9918.