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


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 38131. Перестановка
Темы: Рекуррентные последовательности   

У Беси есть N (3≤N≤40)любимых точек на 2D-решётке, никакие три из которых не коллинеарны. Для каждого 1≤i≤N, i-ая точка задаётся двумя целочисленными координатами xi и yi (0≤xi,yi≤104).
Беси рисует некоторые отрезки между точками следующим образом:

Она выбирает некоторую перестановку p1,p2,…,pN из N точек
Она рисует отрезки между p1 и p2, p2 и p3, p3 и p1.
Затем для каждого целого i от 4 до N по порядку, она рисует отрезки прямых от pi до pj для всех j<i так, этот отрезок не пересекает никакой из ранее нарисованных отрезков (вне конечных точек)
Беси заметила, что для каждого i она нарисовала ровно три новых отрезка. Вычислите количество перестановок, которые Беси могла выбрать на шаге 1, которые удовлетворяют этому свойству по модулю 109+7.

Входные данные: 
Первая строка содержит N.
Каждая из последующих N строк содержит два разделённых пробелом целых числа xi и yi.

Выходные данные: 
Количество перестановок по модулю 109+7.
 

Примеры
№ Входные данные Выходные данные Пояснение
1 4
0 0
0 4
1 1
1 2		 0 Никакая перестановка не сработает.
2 4
0 0
0 4
4 0
1 1		 24 Все перестановки работают.
3 5
0 0
0 4
4 0
1 1
1 2		 96 Одна из перестановок, удовлетворяющих свойству - (0,0),(0,4),(4,0),(1,2),(1,1).
Для этой перстановки
  • Сначала она рисует отрезки между каждой парой (0,0),(0,4), и (4,0).
  • Затем она рисует отрезки от (0,0), (0,4), и (4,0) до (1,2).
  • Наконец, она рисует отрезки от (1,2), (4,0), и (0,0) до (1,1).
Рисунок:

Перестановка не удовлетворяет свойству, если её первые четыре точки (0,0)(0,0), (1,1)(1,1), (1,2)(1,2), и (0,4)(0,4) в некотором порядке.

ID 38639. Мячик на лесенке
Темы: Динамическое программирование: один параметр    Рекуррентные последовательности   

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


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

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


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

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

Примеры
№ Входные данные Выходные данные
1 4 7

ID 21780. MTN DEW
Темы: Динамическое программирование    Рекуррентные последовательности    Динамическое программирование: один параметр   

Чтобы подготовиться к предстоящей битве Bonkisilver должен прокачать свой скил, а, как известно, лучшим способом это сделать, является употребление mtn dew при прослушивании дабстепа в 4:20 по МСК. Полученный скилл вычисляется по формуле:

f(n) = f(n - 1) + f(n - 2) + f(n / 2),
где n - количество литров mtn dew, выражаемое целым числом. Операция n/2 означает целочисленное деление числа n на 2.

Также, известно, что

f(1) = 1 microCoinZ 
f(x) = 0 microCoinZ, при x < 1.

Помогите Bonkisilver сосчитать полученное количество microCoinZ.
 
Входные данные
На вход подается число n (0 <= n <= 70).
 
Выходные данные
Выведите одно число - полученный скилл. 
 
Примеры
№ Входные данные Выходные данные
1 1 1

PS: Mountain Dew, также MTN DEW — безалкогольный сильногазированный прохладительный напиток, торговая марка американской компании PepsiCo. 
ID 25962. Числа Фибоначчи
Темы: Динамическое программирование    Рекуррентные последовательности   

Числа Фибоначчи определяются рекуррентной формулой:

\(F_0 = F_1 = 1, \\ F_n = F_{n-1} + F_{n-2}, \ при\ n > 2\)

Входные данные
В единственной строке входных данных записано натуральное число n (\(1<=n<=45\)).
 
Выходные данные
Вывести одно n-е число Фибоначчи - Fn.
 
Примеры
№ Входные данные Выходные данные
1 1 1
2 7 21

ID 27085. Опасные отходы
Темы: Динамическое программирование: один параметр    Рекуррентные последовательности   

При переработке радиоактивных материалов образуются отходы двух типов: А (неопасные) и B (особо опасные). Отходы каждого типа упаковываются в контейнеры, а затем контейнеры складываются в стопки. Стопка считается взрывоопасной, если в ней есть три или больше контейнеров с особо опасными отходами (типа B) расположены рядом. Для заданного количества контейнеров N определите, сколько есть способов составить безопасную стопку.
 
Входные данные
Входная строка содержит натуральное число – количество контейнеров N в стопке (1 <= N <= 35).
 
Выходные данные
Программа должна вывести одно число – количество способов составить безопасную стопку из N контейнеров.

 
Примеры
№ Входные данные Выходные данные
1 3 7

ID 46789. Счетовод - 1
Темы: Рекуррентные последовательности   

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

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

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

Примеры
№ Входные данные Выходные данные
1 1
2
1
10		 14

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 <= 103, B и C - различные числа)

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

Примеры
№ Входные данные Выходные данные
1 1
2
3
1
18		 96

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 - различные числа)

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

Примеры
№ Входные данные Выходные данные
1 1
2
3
1
12		 225

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 <= 103)

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

Примеры
№ Входные данные Выходные данные
1 1
2
2
38		 266

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). 

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

Примеры
№ Входные данные Выходные данные
1 26
49		 22