Question

Задача 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())

min = 10**5

for i in range(n):

  element = int(input())

  if element < min:

      min = element

print((n-1) * min)

Объяснение:

Answer 2

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

Заметим, что если число K делит число N, то мы можем достичь числа N, нажимая только кнопку умножения на K. Поэтому наша первая цель - увеличить число на дисплее до ближайшего числа, которое делится на K. Мы будем продолжать нажимать кнопку умножения, пока не достигнем этого числа.

После этого мы можем разделить число на дисплее на K, чтобы получить новое число, которое также должно быть достигнуто наименьшим количеством нажатий. Мы будем продолжать делить число на дисплее на K, пока оно делится на K.

Алгоритм решения задачи следующий:

1. Инициализируем счетчик нажатий count = 0.
2. Пока число на дисплее больше 0:
   • Если число на дисплее делится на K, то делим его на K и увеличиваем count на 1.
   • Иначе увеличиваем число на дисплее на 1 и увеличиваем count на 1.
3. Выводим значение count.

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

Ниже приведена реализация данного алгоритма на языке Python:

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

count = 0
while N > 0:
    if N % K == 0:
        N //= K
        count += 1
    else:
        N -= 1
        count += 1

print(count)

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