e-olymp 421. Йо-йо

Задача

Игрушка йо-йо состоит из катушки, на которую намотана нитка. Если, держа за конец нитки, отпустить катушку, то она будет, вращаясь, сначала опускаться вниз, а затем по инерции подниматься вверх. Но высота, на которую катушка поднимется, будет в $k$ раз меньше, чем высота, с которой она опустилась. Будем считать, что катушка остановилась, если высота её очередного подъема не превышает $1$.

Напишите программу, которая по длине нитки $l$ и коэффициенту $k$ считает количество подъемов катушки до остановки. Например, пусть $l = 17$ и $k = 2$, тогда катушка будет подниматься на высоты $8.5$, $4.25$, $2.1254$, $1.0625$, а затем остановится. Таким образом получится $4$ подъема.

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

Два целых числа $l (1 ≤ l ≤$ 109$)$ и $k (2 ≤ k ≤ 100)$.

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

Вывести одно число – количество подъемов.

Тесты

Ввод Вывод
1 17 2 4
2 4 2 1
3 135 9 2
4 1 2 0
5 1000000000 100 4

Код программы

Решение

Для решения данной задачи достаточно найти максимальную степень $k$, которая будет меньше числа $l$. Значение показателя степени и будет количеством подъемов йо-йо. Ответ найдем с помощью логарифма, подключив библиотеку <cmath>. Используем формулу перехода логарифма к новому основанию, а каким будет это основание значения не имеет. Заметим, что нас интересует только целая часть логарифма — число подъемов.

Также необходимо учесть, что кaтушка остановится в случае, если высота её очередного подъема будет меньше либо равна $1$. Это означает, что, если $l$ будет степенью $k$, полученный с помощью логарифма ответ будет на единицу больше верного. Введем очень маленькую константу с для разрешения этой проблемы. На ответ она особо не повлияет, а вот от единицы поможет избавиться.

Ссылки

Решение задачи на Ideone

Задача 421 на e-olymp

Related Images: