Рекуррентные последовательности

ID 80754. Непизанские кролики (2024-2025, 11)

Дана блок-схема алгоритма, реализованного в виде рекурсивно вызываемой функции:

Известно, что 𝐴, 𝐵 и 𝐶 - натуральные числа и что 𝐴 < 𝐵 < 𝐶.
Петя вызывает эту функцию, передавая ей в качестве входного параметра натуральное число. Известно, что для некоторого 𝑘 функция возвращает следующие значения:
𝐹(𝑘) = 50890368413;
𝐹(𝑘 + 1) = 93601980590;
𝐹(𝑘 + 2) = 172160883161.
Определите значения 𝐴, 𝐵 и 𝐶, при которых это возможно. Если таких вариантов несколько, выберите вариант с наименьшей суммой 𝐴, 𝐵 и 𝐶. В ответе введите в указанном порядке значения 𝐴, 𝐵 и 𝐶, разделённые пробелом.
 

ID 63700. Рекурсия

Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n, если n < 11,
F(n) = n + F(n­ –1), если n ≥ 11

По заданным числам A и B вычислите значение выражения F(A) – F(B)?

Входные данные
А и B вводятся с клавиатуры (2000 <= A, B <= 5000). Каждое число в отдельной строке.

Выходные данные
Выведите ответ на задачу.
 

Примеры

ID 55456. Треугольник Паскаля

Треугольник Паскаля строится следующим образом. Первая строка состоит из одного числа, равного единице. Каждая следующая содержит на одно число больше, чем предыдущая. Первое и последнееиз этих чисел равны 1, а все остальные вычисляются как сумма числа, стоящего в предыдущей строке над ним и числа, стоящего в предыдущей же строке слева от него.

Входные данные
Вводится одно число N (0<=N<=30).

Выходные данные
Вывести N строк треугольника Паскаля (числа выводятся через пробел).

ID 55381. Хитрая последовательность

Вычислите n-й член последовательности, заданной формулами:

a_2n = a_n + 1 (n>0),
a_2n+2 = a_2n+1 - a_n (n>0),
a₀=1, a₁=1.

Входные данные
Вводится натуральное число n, не превосходящее 1000.

Выходные данные
Выведите ответ к задаче.

ID 55380. Простая последовательность

Вычислите n-й член последовательности, заданной формулами:

a_2n = a_n + a_n-1,
a_2n+1 = a_n – a_n-1,
a₀ = a₁ = 1.

Входные данные
Вводится одно натуральное число n (1≤n≤1000).

Выходные данные
Вывести одно число a_n.

ID 55379. Последняя цифра числа Фибоначчи

Последовательность чисел Фибоначчи определяется следующим образом: F₀ = F₁ = 1,

F_n+1 = F_n+F_n-1. Напишите программу для вычисления последней цифры n-го члена последовательности.

Входные данные
В единственной строке входных данных записано натуральное число n (1≤n≤1000).

Выходные данные
Вывести последнюю цифру числа F_n.

ID 54923. Средняя последовательность

Рассмотрим неубывающую последовательность s₁, ..., s_n + 1 ( s_i <= s_i + 1 для 1 <= i <= n ). Последовательность m₁, ..., m_n, в которой каждый член определен как m_i = ½ * ( s_i + s_i + 1 ) для 1 <= i <= n, назовем “средней последовательностью” для последовательности s₁, ... s_n + 1. Например, средняя последовательность для последовательности 1, 2, 2, 4 есть 1.5, 2, 3. Заметим, что элементы средней последовательности могут быть дробными числами. Тем не менее, в данной задаче используются только те средние последовательности, в которых все числа целые. Для заданной неубывающей последовательности из n целых чисел m1, ..., mn необходимо вычислить количество всех неубывающих последовательностей из n + 1 целых чисел s₁, ..., s_n + 1, для которых заданная последовательность m₁, ..., m_n является средней последовательностью.

Задание
Напишите программу, которая:

• читает из стандартного ввода неубывающую последовательность целых чисел;
• вычисляет количество всех неубывающих последовательностей целых чисел, для которых заданная последовательность является средней последовательностью;
• выводит ответ в стандартный вывод.

Входные данные
Первая строка стандартного ввода содержит одно целое число n (2 <= n <= 5000000). Оставшиеся n строк содержат значения последовательности m₁, ..., m_n. Строка i + 1 содержит одно целое число mi (0 <= mi <= 1000000000).

Выходные данные
Ваша программа должна вывести в стандартный вывод ровно одно целое число – количество всех неубывающих последовательностей целых чисел, для которых входная последовательность является средней последовательностью.

ID 47159. Рекурсия итеративно - 3

Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n, если n < 11,
F(n) = n + F(n­ –1), если n ≥ 11

По заданным числам A и B вычислите значение выражения F(A) – F(B)?

Входные данные
А и B вводятся с клавиатуры (2000 <= A, B <= 5000). Каждое число в отдельной строке.

Выходные данные
Выведите ответ на задачу.
 

Примеры

ID 47158. Рекурсия итеративно - 2

Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 7, если n < 7,
F(n) = n + 1 + F(n­ –2), если n ≥ 7.

По заданным числам A и B вычислите значение выражения F(A) – F(B)?

Входные данные
А и B вводятся с клавиатуры (2000 <= A, B <= 5000). Каждое число в отдельной строке.

Выходные данные
Выведите ответ на задачу.
 

Примеры

ID 47155. Рекурсия итеративно - 1

Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 3, если n < 3,
F(n) = 2n + 5 + F(n­ – 2), если n ≥ 3.

По заданным числам A и B вычислите значение выражения F(A) – F(B)?

Входные данные
А и B вводятся с клавиатуры (2000 <= A, B <= 5000). Каждое число в отдельной строке.

Выходные данные
Выведите ответ на задачу.
 

Примеры

ID 47154. Счетовод - 8

У исполнителя Счетовод две команды, которым присвоены номера:
1. прибавь A
2. умножь на B
3. умножь на С
Первая из них увеличивает на A число на экране, вторая умножает число на экране на B, третья умножает число на экране на С. Программа для Счетовода – это последовательность команд. Сколько существует таких программ, которые исходное число S преобразуют в число F и при этом траектория вычислений программы содержит число num и не содержит число misnum?

Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F, B не равно C.

Входные данные
Программа получает на вход семь чисел в следующем порядке: A, B, C, S, F, num, misnum (1<= A <= 10, 2 <= B,C <= 10, 1 <= S <= 100, 1 <= F <= 10³, S <= num < misnum <= F). Каждое число вводится с новой строки.

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263.
 

Примеры

ID 47152. Счетовод - 7

У исполнителя Счетовод две команды, которым присвоены номера:
1. вычти A
2. вычти B
3. подели на С
Первая из них уменьшает на A число на экране, вторая уменьшает число на экране на B, третья делит целочисленно число на экране на С (с отбрасыванием остатка, в случае, если число на экране не делится на С). Программа для Счетовода – это последовательность команд. Сколько существует таких программ, которые исходное число S преобразуют в число F и при этом траектория вычислений программы содержит число num1 и число num2?

Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F, A не равно B.

Входные данные
Программа получает на вход семь чисел в следующем порядке: A, B, C, S, F, num1, num2 (1<= A,B,C <= 10, 1 <= S <= 100, 1 <= F <= 10³, S >= num1 > num2 >= F). Каждое число вводится с новой строки.

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263.
 

Примеры

ID 47145. Счетовод - 6

У исполнителя Счетовод две команды, которым присвоены номера:
1. прибавь A
2. прибавь B
3. умножь на С
Первая из них увеличивает на A число на экране, вторая увеличивает число на экране на B, третья умножает число на экране на С. Программа для Счетовода – это последовательность команд. Сколько существует таких программ, которые исходное число S преобразуют в число F и при этом траектория вычислений программы содержит число num1 и число num2?

Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F, A не равно B.

Входные данные
Программа получает на вход семь чисел в следующем порядке: A, B, C, S, F, num1, num2 (1<= A,B,C <= 10, 1 <= S <= 100, 1 <= F <= 10³, S <= num1 < num2 <= F). Каждое число вводится с новой строки.

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263.
 

Примеры

ID 47128. Счетовод - 5

У исполнителя Счетовод две команды, которым присвоены номера:
1. прибавь 1
2. сделай четное
3. сделай нечетное
Первая из них увеличивает на 1 число на экране, вторая умножает это число на 2, третья переводит число x в число 2x + 1. Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21. 
Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F.

Входные данные
Программа получает на вход два числа: S, F (1 <= S <= 100, 1 <= F <= 10³)

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263.
 

Примеры

ID 46804. Счетовод - 5

У исполнителя Счетовод две команды, которым присвоены номера:
1. прибавь 1
2. увеличь каждый разряд числа на 1

Первая команда увеличивает число на 1, вторая - увеличивает каждый разряд числа на 1, если он не равен 9. 
Например, число 45 с помощью команды 2 превратится в 56, а 49 в 59 (так как младший разряд равен 9 и он остается без изменений).
Программа для Счетовода – это последовательность команд.
Сколько существует программ, которые число S преобразуют в число F? 


Входные данные
Программа получает на вход два числа (каждое число записано в отдельной строке): S и F ( 1 <= S <= 100, 10 <= F <= 1000, S < F). 

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263.
 
 

Примеры

ID 46792. Счетовод - 4

У исполнителя Счетовод две команды, которым присвоены номера:
1. прибавь A
2. умножь на B
3. возведи в квадрат
Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F.

Входные данные
Программа получает на вход четыре числа: A, B, S, F (1 <= A, B <= 10, 1 <= S <= 100, 1 <= F <= 10³)

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263.
 

Примеры

ID 46791. Счетовод - 3

У исполнителя Счетовод три команды, которым присвоены номера:
1. прибавь A
2. прибавь B
3. умножь на С
Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F.

Входные данные
Программа получает на вход четыре числа: A, B, С, S, F (1 <= A, B, C <= 10, 1 <= S <= 10, 1 <= F <= 100, A и B - различные числа)

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263.
 

Примеры

ID 46790. Счетовод - 2

У исполнителя Счетовод три команды, которым присвоены номера:
1. прибавь A
2. умножь на B
3. умножь на С
Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F.

Входные данные
Программа получает на вход пять чисел: A, B, С, S, F (1 <= A, B, C <= 10, 1 <= S <= 100, 1 <= F <= 10³, B и C - различные числа)

Выходные данные
Выведите ответ на задачу.  Гарантируется, что ответ не превышает 263.

Примеры

ID 46789. Счетовод - 1

У исполнителя Счетовод две команды, которым присвоены номера:
1. прибавь A
2. умножь на B
Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F.

Входные данные
Программа получает на вход четыре числа: A, B, S, F (1 <= A, B <= 10, 1 <= S <= 100, 1 <= F <= 10³)

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263.
 

Примеры

ID 38639. Мячик на лесенке

На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных "маршрутов" мячика с вершины на землю.

Вводится одно число 0 < N < 31.

Выведите одно число — количество маршрутов.
 

Примеры