Question

Задача 6: Странное устройство Полный балл: 100 Ограничение времени: 1 с Ограничение памяти: 512M Ограничение размера стека: 64M По приезде Василий с Петром обнаружили в своем номере в гостинице странный прибор. Он был оснащен дисплеем, на котором показывалось число 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

Ответ:

var

b , K , N ,a:longint;

Begin

read(N);

read(K);

a:= N div K ;  

b:= N mod K ;

if K>N

 then write (N);

if K=N

 then write (2);

if K<N

 then write(1 +a +b);

end.

Объяснение:Сразу говорю: код не мой, на 80 баллов сдаётся, написан на паскале(free pascal)

Answer 2

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

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

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

pythonCopy code
def strange_device(N, K):
    count = 0
    while N > 0:
        if N % K == 0:
            N = N // K
            count += 1
        else:
            count += N % K
            N -= N % K
    return count

N = int(input())
K = int(input())
result = strange_device(N, K)
print(result)

Пример работы программы:

Copy code
Входные данные:
10
2

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

В этом примере мы хотим получить число 10, используя устройство с K = 2. Мы можем сделать следующие операции:

• Умножить число 0 на 2 (1 нажатие).
• Увеличить число на 1 (2 нажатия).
• Умножить число 1 на 2 (3 нажатия).
• Умножить число 2 на 2 (4 нажатия).

Таким образом, минимальное количество нажатий равно 4.