Question

СРООООЧНО НА ПИТОНЕ 40 баллов Сдать решение задачи 6-Странное устройство Полный балл: 100 Ограничение времени: 1 с Ограничение памяти: 512M Ограничение размера стека: 64M Задача 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 баллов. Пример Ввод Вывод Пояснение 4 2 3 Василий и Петр хотят воспроизвести число 4. Кнопка умножает на 2 число, которое показывается на дисплее. Первой операцией друзья увеличивают текущее число на 1, нажимая первую кнопку, после чего оно становится равно 1. Затем они умножают его на 2, нажимая вторую кнопку. Текущее число становится равно 2. После чего, для получения на дисплее числа 4 достаточно один раз нажать вторую кнопку и умножить текущее число (то есть 2) на 2. Несложно показать, что меньше, чем за три операции, получить число 4 невозможно. Таким образом, минимальное число действий равняется трем.

Answer 1

Python 3.x:

n = int(input())

k = int(input())

total = 0

while n > 0:

   if n % k == 0:

       n = n / k

   else:

       n -= 1

   total += 1

print(total)

Answer 2

Решение:

Для начала заметим, что умножение числа на $K$ эквивалентно последовательным прибавлениям к этому числу числа $1$ $K$ раз. Таким образом, мы можем считать, что у нас есть только две операции: увеличить число на $1$ и увеличить число на $K$.

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

Для начала заметим, что мы всегда можем получить любое число, которые меньше или равно $K$, с помощью первой операции. Если $N \leq K$, то мы можем просто $N$ раз нажать на первую кнопку и получить число $N$. Далее будем считать, что $N > K$.

Рассмотрим два случая:

1. $K = 2$

В этом случае мы можем использовать бинарное представление числа $N$, чтобы получить оптимальную последовательность действий. Если бит $i$ числа $N$ равен $0$, то мы просто нажимаем первую кнопку. Если же он равен $1$, то мы умножаем текущее число на $2$ и затем нажимаем первую кнопку. Таким образом, мы за $\log_2 N$ операций получим число $N$.

2. $K > 2$

В этом случае мы можем строить все возможные последовательности действий и выбирать из них наименьшую. Будем поддерживать текущее число и число операций, выполненных над ним. Начинаем с числа $0$ и количества операций $0$. Добавляем две новые последовательности действий: увеличить текущее число на $1$ и увеличить текущее число на $K$. Для каждой из этих последовательностей проверяем, не получили ли мы уже такое же число раньше (чтобы избежать зацикливания). Если нет, то добавляем новые последовательности действий для каждой из двух операций. Повторяем этот процесс до тех пор, пока не найдем число $N$.

Заметим, что в худшем случае мы переберем все числа из диапазона $[0, N-1]$. Количество таких чисел равно $N$, поэтому временная сложность нашего алгоритма составляет $O(N)$. Однако, на практике мы будем добавлять новые последовательности действий только для чисел, которые мы еще не видели, что должно заметно уменьшить реальное количество итераций цикла.

Итак, реализуем оба алгоритма и выберем тот, который работает быстрее в зависимости от значения $N$ и $K$. Если $K = 2$, то выбираем первый алгоритм, иначе - второй.

Код решения:

```python
def strange_device_1(N, K):
# Алгоритм для K = 2
res = 0
while N > 0:
if N % 2 == 0:
N //= 2
else:
N -= 1
res += 1
return res

def strange_device_2(N, K):
# Алгоритм для K