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 баллов. Пример Ввод Вывод Пояснение 4 2 3 Василий и Петр хотят воспроизвести число 4. Кнопка умножает на 2 число, которое показывается на дисплее. Первой операцией друзья увеличивают текущее число на 1, нажимая первую кнопку, после чего оно становится равно 1. Затем они умножают его на 2, нажимая вторую кнопку. Текущее число становится равно 2. После чего, для получения на дисплее числа 4 достаточно один раз нажать вторую кнопку и умножить текущее число (то есть 2) на 2. Несложно показать, что меньше, чем за три операции, получить число 4 невозможно. Таким образом, минимальное число действий равняется трем.

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.

Объяснение:free pascal

Answer 2

Problem Analysis

Vasiliy and Petr have found a strange device in their hotel room with a display showing the number 0 and two buttons. One button increases the number on the display by 1, and the other multiplies it by K. They want to reproduce a given number N on the display with the minimum number of button presses.

Approach

To solve this problem, we need to find the minimum number of button presses required to reach the number N on the display. We can achieve this by simulating the process of reaching N from 0 using the given operations.

Solution

To find the minimum number of button presses, we can use the following approach: 1. Initialize a variable to store the count of button presses. 2. While the current number on the display is less than N: - If (current number + 1) * K is less than or equal to N, increment the current number by 1. - Otherwise, multiply the current number by K. - Increment the count of button presses. 3. Return the count of button presses as the minimum number of presses required to reach N.

Let's implement this approach in code.

Code Implementation

```python def min_button_presses(N, K): count = 0 current_number = 0 while current_number < N: if (current_number + 1) * K <= N: current_number += 1 else: current_number *= K count += 1 return count

# Example usage N = 4 K = 2 result = min_button_presses(N, K) print(result) # Output: 3 ```

Explanation

In the given example, Vasiliy and Petr want to reproduce the number 4 on the display using the device with K=2. The minimum number of button presses required to reach 4 on the display is 3, as explained in the problem statement.

Feel free to ask if you have any further questions or need additional assistance!