Срочно дам 50 балов Задача 6: Странное устройство

По приезде Василий с Петром обнаружили в своем номере в гостинице странный прибор. Он был оснащен дисплеем, на котором показывалось число 0, и двумя кнопками. Василий сразу понял, что первая кнопка увеличивает число на дисплее на 1, а вторая умножает его на K. В этот момент Петр обнаружил на своей кровати листок бумаги, на котором было написано единственное число N.

Теперь друзья хотят воспроизвести число N на дисплее найденного ими устройства, и, поскольку их ждет еще множество дел, им интересно минимальное число нажатий на кнопки устройства для получения числа N.

Входные данные

• В первой строке входных данных указано целое неотрицательное число N (1 ≤ N ≤ 109).
• Во второй строке входных данных указано целое положительное число K (2 ≤ K ≤ 109).

Выходные данные

Выведите единственное число — минимальное количество нажатий на кнопки устройства для получения на его дисплее числа N.

Система оценки

• Решения, работающие при K = 2, будут набирать не менее 20 баллов.
• Решения, работающие при N ≤ 20, будут набирать не менее 15 баллов.
• Решения, работающие при N ≤ 105, будут набирать не менее 35 баллов.

Пример

Информатика 9 класс Алгоритмы и структуры данных информатика странное устройство минимальное количество нажатий число n кнопки устройства увеличение числа умножение на K алгоритм решения оптимизация нажатий задачи по информатике Новый

Чтобы решить задачу, давайте проанализируем, как можно получить число N на дисплее устройства с помощью двух кнопок: одной, которая увеличивает число на 1, и другой, которая умножает текущее число на K.

Мы можем подойти к решению этой задачи с помощью обратного мышления. Вместо того, чтобы думать, как увеличить число с 0 до N, мы можем рассмотреть, как можно уменьшить N до 0, используя те же операции, но в обратном порядке.

Вот шаги, которые нужно выполнить:

1. Инициализируем счетчик нажатий кнопок, который будет равен 0.
2. Пока N больше 0, выполняем следующие действия:
• Если N делится на K (т.е. N % K == 0), то:
• Делим N на K (N = N / K).
• Увеличиваем счетчик нажатий на 1.
• Если N не делится на K, то:
• Вычитаем 1 из N (N = N - 1).
• Увеличиваем счетчик нажатий на 1.

Когда N станет равным 0, мы завершаем процесс. Счетчик нажатий будет содержать минимальное количество нажатий кнопок, необходимых для достижения числа N.

Теперь давайте рассмотрим пример:

Пример:

Пусть N = 10, K = 2.

Шаги:

1. 10 делится на 2, делим 10 на 2, получаем 5 (нажатий: 1).
2. 5 не делится на 2, вычитаем 1, получаем 4 (нажатий: 2).
3. 4 делится на 2, делим 4 на 2, получаем 2 (нажатий: 3).
4. 2 делится на 2, делим 2 на 2, получаем 1 (нажатий: 4).
5. 1 не делится на 2, вычитаем 1, получаем 0 (нажатий: 5).

Итак, минимальное количество нажатий для получения 10 при K = 2 равно 5.

Теперь вы можете реализовать этот алгоритм в коде, чтобы получить ответ для любых значений N и K.