решите данную задачу:
Рома, увидев результаты последнего тура, рассердился и начал рвать листочек с условиями задач на кусочки. Он занимался этим t секунд (возможно, ноль) - каждую секунду брал первый попавшийся кусочек листа и рвал его на k частей. В итоге Рома обнаружил перед собой n обрывков листа. Рома потерял себя в акте этой необоснованной агрессии, поэтому просит вас по числам n и k восстановить минимальное подходящее число t
.
Формат входных данных
В первой строке входных данных содержатся два целых числа n и k (1≤n,k≤10^9 ).
Формат выходных данных
Выведите искомое минимальное подходящее число t , если его не существует, то −1.
input: output:
10 4 3
10 3 -1
Python
Начинаем мы с одной части - целого листа.
Код на python
n, k = map(int, input())
if k == 1 and n == 1: print(0)
elif k == 1 or (n - 1) % (k - 1) != 0: print(-1)
else: print((n - 1) // (k - 1))
Если мы берём часть и рвём её на k частей, общее кол-во частей увеличивается на k - 1.Начинаем мы с одной части - целого листа.
Для решения этой задачи можно использовать бинарный поиск. Мы знаем, что t должно быть неотрицательным целым числом, поэтому мы можем использовать бинарный поиск для поиска минимального t, при котором количество обрывков листа будет не меньше n.
Вот код на Python:
```python
def count_pieces(t, k):
pieces = 0
for i in range(t):
pieces += k ** i
return pieces
def min_time(n, k):
left = 0
right = n
while left < right:
mid = (left + right) // 2
pieces = count_pieces(mid, k)
if pieces < n:
left = mid + 1
else:
right = mid
return left
n = int(input("Введите количество обрывков листа: "))
k = int(input("Введите количество частей, на которые рвется каждый кусочек: "))
t = min_time(n, k)
print("Минимальное подходящее число t: ", t)
```
Пример работы программы:
```
Введите количество обрывков листа: 10
Введите количество частей, на которые рвется каждый кусочек: 2
Минимальное подходящее число t: 4
```
Это означает, что если Рома будет рвать листок на части каждую секунду в течение 4 секунд, то он получит не менее 10 обрывков листа.
Вот код на Python:
```python
def count_pieces(t, k):
pieces = 0
for i in range(t):
pieces += k ** i
return pieces
def min_time(n, k):
left = 0
right = n
while left < right:
mid = (left + right) // 2
pieces = count_pieces(mid, k)
if pieces < n:
left = mid + 1
else:
right = mid
return left
n = int(input("Введите количество обрывков листа: "))
k = int(input("Введите количество частей, на которые рвется каждый кусочек: "))
t = min_time(n, k)
print("Минимальное подходящее число t: ", t)
```
Пример работы программы:
```
Введите количество обрывков листа: 10
Введите количество частей, на которые рвется каждый кусочек: 2
Минимальное подходящее число t: 4
```
Это означает, что если Рома будет рвать листок на части каждую секунду в течение 4 секунд, то он получит не менее 10 обрывков листа.
Павел Дуров
не работает, всегда выдаёт -1
Похожие вопросы
- Можете помочь! Нужен код для Python, что бы он заменял определенный текст в файле
- Можно ли создать свой редактор кода на PYTHON?
- Проблема с кодом в Python
- НАПИШИТЕ СРОЧНО КОД НА PYTHON!
- Проблема с кодом на Python
- Код на Python
- Объясните код на python pytelegrambotapi
- Помогите с кодом в python
- Информатика. Код для Python
- Ошибка в коде на Python