Question

ДАЮ 30 БАЛЛОВ. Задача 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 баллов.

Answer 1

Ответ:

n = int(input())

k = int(input())

res = 0

while n > 0:

   n = n / k if n % k == 0 else n - 1

   res += 1

print(res)

Объяснение:

Только 70 балов даёт( Но это же лучше чем ничего?!

Answer 2

Для решения этой задачи можно использовать жадный алгоритм. Мы можем постепенно увеличивать число на дисплее до достижения значения N.

Вот пример решения на языке Python:

pythonCopy code
N = int(input())
K = int(input())

count = 0

while N > 0:
    remainder = N % K
    count += remainder
    N //= K
    count += 1

count -= 1  # уменьшаем счетчик на 1, так как последнее действие (умножение на K) не требуется

print(count)

Это решение работает при любых значениях N и K. Оно выполняет деление числа N на K до тех пор, пока N не станет равным 0, одновременно увеличивая счетчик на остаток от деления. Затем уменьшает счетчик на 1, так как последнее действие (умножение на K) не требуется.

Например, если N = 21 и K = 2, то минимальное количество нажатий будет равно 5. Последовательность действий будет следующей: 0 -> 1 -> 2 -> 4 -> 8 -> 16 -> 21.

Данное решение работает с временной сложностью O(log N), где N - входное число.