Условие задачи
Вычислите функцию:

[latex]f(n)=\begin{cases} 1, \text{ если } n \leq 2 \\ f(\lfloor \frac{6\cdot n}{7} \rfloor)+f(\lfloor \frac{2\cdot n}{3} \rfloor), \text{ если } n \mod \; 2 = 1 \\ f(n-1)+f(n-3), \text{ если } n \mod \; 2 = 0 \end{cases}[/latex]

Входные данные
Одно натуральное число [latex] n \; [/latex] [latex](1 \leq n \leq 10^{12}) [/latex].

Выходные данные
Значение [latex] f(n) [/latex], взятое по модулю [latex] 2^{32} [/latex].

Тесты

Входные данные	Выходные данные
[latex]10[/latex]	[latex]7[/latex]
[latex]123[/latex]	[latex]229966[/latex]
[latex]1[/latex]	[latex]1[/latex]
[latex]100[/latex]	[latex]136345[/latex]
[latex]51[/latex]	[latex]5092[/latex]
[latex]1985[/latex]	[latex]3905609318[/latex]

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

Решение задачи
Решение данной задачи стоит начать с написания рекурсивной функции для вычисления функций по условию задачи. Так как рекурсия будет довольно таки сложной и много раз повторяются одни и те же результаты при вызове функции, следовательно, программа будет долгое время обрабатывать нашу задачу. То есть, к примеру, на 5 и 20 итерации, возвращаемые значения функции могут совпасть, что без оптимизации будет просчитываться еще раз, а с оптимизацией функция уже знает, чему равно значение с данными аргументами. (Наглядно видно на картинке) Для того, чтобы этого не было, нам надо использовать Мемоизацию(сохранение результатов выполнения функции для увеличения скорость выполнения). Еще надо не забывать про тип данных, надо использовать long long, потому что у нас по условию очень большое число. Функция должна возвращать unsigned int, потому что в int не хватает области значений.(наша функция на каком-то этапе будет возвращать число больше двух миллиардов, для int — это выход за предел.) Далее, по условию, мы пишем наконец нашу функцию:

• Если число, которое ввел пользователь, меньше либо равно двум, то наша функция возвращает значение один.
• Если есть значение с таким же ключом, то оно возвращает значение.
• Если число, которое ввел пользователь, дает остаток от деления один, то наша функция возвращает значение [latex] f(\lfloor \frac{6\cdot n}{7} \rfloor)+f(\lfloor \frac{2\cdot n}{3} \rfloor)[/latex].
• Во всех остальных случаях наша функция возвращает значение [latex] f(n-1)+f(n-3) [/latex].

Самое сложное сделали, осталось в main инициализировать переменную(не забывая про её тип), обработать её функцией и вывести на экран.

Ссылки

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

Related Images: