Жетоны на автобус: пачки по степеням 7

В городе школьникам продают автобусные жетоны не по одному, а пачками. Есть пачки размеров:

1, 7, 49, 343, 2401, ... (то есть 7^0, 7^1, 7^2, 7^3, ...).

Пачек каждого размера сколько угодно. Ты хочешь купить ровно S жетонов так, чтобы пачек было как можно меньше.

Замечание: S может не помещаться в 32-битный тип (как на олимпиадах), но в Python это не проблема.

Формат ввода

Одно целое число S.

Формат вывода

Выведите одно целое число — минимальное количество пачек, которыми можно набрать ровно S жетонов.

Ограничения

• 0 ≤ S ≤ 10^9
• Пачки: 7^k для k ≥ 0, количество каждого размера не ограничено.

Пример

Ввод:

100

Вывод:

4

Пояснение: 100 = 98 + 2 = 2·49 + 2·1, нужно 4 пачки.

Ключевое наблюдение: размеры пачек — это степени 7. Значит, любое число S можно единственным образом разложить как S = a0*7^0 + a1*7^1 + a2*7^2 + ..., где 0 <= ai <= 6 — это ровно цифры S в 7-ричной записи.

Почему это даёт минимум пачек: если у вас есть 7 пачек размера 7^k, их всегда можно заменить на 1 пачку размера 7^(k+1) и уменьшить число пачек на 6. Поэтому в оптимальном наборе никогда не нужно брать по 7 (или больше) одинаковых пачек одного размера — коэффициенты при 7^k должны быть от 0 до 6. А такая «нормальная форма» как раз и есть 7-ричная запись, и число пачек равно a0 + a1 + a2 + ....

План решения:

• Прочитать S.
• Пока S > 0:
• Взять последнюю 7-ричную цифру d = S % 7.
• Прибавить d к ответу (столько пачек размера 7^k нужно).
• Убрать последнюю цифру: S //= 7.
• Вывести накопленную сумму.

Мини-сниппет (сердце идеи): ans += S % 7 S //= 7

Сложность: O(log_7 S) операций, память O(1).

Частая ошибка: пытаться «жадно» просто вычитать самую большую степень 7 по одной пачке — это тоже работает, но медленнее; лучше сразу брать остаток S % 7, иначе легко сделать лишние шаги и запутаться.