Задача взята с сайта e-olymp.
Задача
Как-то наконец земляне нашли обитаемую планету, назвали ее ТТВ, и отправили вместе с кораблем туда одного кролика. Кролику понравился климат новой планеты и через месяц он произвел на свет еще одного кролика. Известно, что каждый месяц каждый кролик, присутствующий на планете, производил на свет еще одного кролика. На планете откуда-то взялся монстр, который в начале месяца съедал [latex] k [/latex] кроликов, если только их становилось строго больше [latex] k [/latex]. В задаче необходимо определить количество кроликов, которое будет на планете через [latex] n [/latex]месяцев после прибытия туда космического корабля с первым кроликом.
Входные данные
Первая строка содержит количество месяцев [latex] n [/latex] [latex] (0 ≤ n ≤ 100) [/latex], вторая — число кроликов [latex] k [/latex] [latex] (0 ≤ k ≤ 10000) [/latex], которое съедал монстр.
Выходные данные
Определить количество кроликов, которое будет находиться на планете ТТВ через [latex] n [/latex] месяцев после поселения туда первого кролика. Известно, что результат для любого теста всегда не больше [latex] 2 \cdot 10^9 [/latex].
Тесты
| # | Входные данные | Выходные данные |
|
1 |
0 10 |
1 |
|
2 |
1 10 |
2 |
|
3 |
10 7 |
128 |
|
4 |
7 128 |
12 |
|
5 |
30 0 |
1073741824 |
|
6 |
29 29 |
2 |
|
7 |
20 20 |
16 |
|
8 |
90 90 |
64 |
Cпособ 1 (с циклом)
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#include <iostream> using namespace std; int main() { long int r = 1, n, k; cin >> n >> k; for (int i = n; i > 0; i--){ if (r > k) r -= k; r *= 2; } cout << r; return 0; } |
Решение
Известно, что изначально на планете был один кролик. Создадим цикл, который будет высчитывать популяцию кроликов на планете через [latex] n [/latex] месяцев после прибытия. Цикл будет работать до тех пор, пока количество месяцев будет больше нуля. В нем будем высчитывать популяцию кроликов по простой формуле [latex] r = r \cdot 2 [/latex], где [latex] r [/latex] — количество кроликов. Если же количество кроликов, съедаемых монстром в начале месяца строго больше того количества, которое уже есть на планете, то от этой популяции отнимем [latex] k [/latex]кроликов : [latex] r = r[/latex] $-$ [latex] k [/latex]. Внутри цикла также не забываем от данного количества [latex] n [/latex] месяцев отнимать по одному каждый раз.
Способ 2 (без цикла)
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include <iostream> using namespace std; int f2(long int r, long int n, long int k){ if (n == 0) return r; if (r <= k) return f2(r * 2, n - 1, k); return f2(2 * (r-k), n - 1, k); } int main() { long int n, k, r = 1; cin >> n >> k; cout << f2(r, n, k); return 0; } |
Решение
Сам алгоритм похож на 1 способ, однако здесь мы будем использовать рекурсивную функцию, а не цикл. Функция int f2(); будет вызывать сама себя до тех пор, пока количество месяцев [latex] n [/latex] не станет равным нулю.
Ссылки
Засчитанное решение на e-olymp.
1 Код в ideone.
2 Код в ideone.
Спасибо за замечания, все исправил.
Добавим интриги к этой задаче. Допустим:
1. n <= 10^9, k <= 10^9
2. n <= 10^18, k <= 10^18
Сможете решить при таких ограничениях? А без циклов?
Можно попробовать через unsigned long long, но при таких значениях будет очень нагружена программа. Цикл можно заменить рекурсивной функцией как во 2 способе, но на нагруженность программы это тоже особо не повлияет…
Не очень понятно, зачем Вы вводите новое понятие «нагруженность программы».
Совершенно очевидно, что решения задачи являются периодическими по $n$. Это простое наблюдение позволит легко решить расширенный вариант, предложенный Олегом.
