e-olymp 7367. Спортсмен

Задача

Спортсмен в первый день пробежал 10 км. Каждого следующего дня он увеличивал норму на 10% от нормы предыдущего дня. Опредилить через какое найменьшее количество дней спортсмен пробежит сусмарный путь не меньший чем [latex]N[/latex] км.

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

Целое число [latex]N (0 < N≤ 1000)[/latex].

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

Единственное число – количество дней.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 9 1
2 45 4
3 324 16
4 1234 28
5 213213123 153

Код программы №1 (с использованием цикла):

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

Сначала вводим 4 переменные: [latex] k=1 [/latex] ( количество дней ), [latex] T=10 [/latex] ( количество километров которое спортсмен пробежал ), [latex] N [/latex] ( количество километров которое спортсмен должен пробежать ) и [latex] S [/latex] ( количество километров которое спортсмен пробегает в день ). Цикл каждый раз будет прибавлять к расстоянию которое пробежал спортсмен, количество километров которое спортсмен должен пробежать в течение следующего дня, с учетом того, что каждый день он будет пробегать на [latex] 10 [/latex] процентов больше, чем в прошлый день, параллельно увеличивая количество дней, пока [latex] N [/latex] будет больше [latex] T [/latex]. Если же [latex] N [/latex] при вводе изначально будет меньше [latex] T [/latex], то программа выведет, что спортсмену достаточно одного дня.

  • Время срабатывания программы при [latex]N = 1000[/latex] : [latex]65[/latex] [latex]ms[/latex]

 

Ссылки

  • Задача на сайте e-olymp
  • Код решения в Ideone

Код программы №2(с использованием линейных вычислений):

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

Также данную задачу можно решить с помощью формулы геометрической прогрессии [latex]S=\frac{b_1(q^n-1)}{q-1}[/latex] из которой нам нужно будет выразить степень [latex] n [/latex] через логарифм при условии того, что по условию задачи мы знаем, что [latex] q=1.1 [/latex] и [latex] b_1=1 [/latex]. И мы получаем, что [latex] \left(n=\log_{1.1}\left(\frac{s}{100}+1\right)\right) [/latex]. При записи логарифма по основанию в С++ мы пользуемся основным свойством логарифмов: [latex] \log_{a}\left(b\right)=\frac{\log_{c}\left(b\right)}{\log_{c}\left(a\right)} [/latex]. Также используем функцию сeil, которая округлит выходное число вверх, до ближайшего целого. ( [latex] S [/latex] — количество километров, которое должен пробежать спортсмен ).

  • Время срабатывания программы при [latex]N = 1000[/latex] : [latex]76[/latex] [latex]ms[/latex]

Ссылки