Условие задачи | | Прогресс |
Темы:
Рекуррентные последовательности
У Беси есть 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) в некотором порядке. |
| |
|
Темы:
Динамическое программирование: один параметр
Рекуррентные последовательности
На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных "маршрутов" мячика с вершины на землю.
Входные данные
Вводится одно число 0 < N < 31.
Выходные данные
Выведите одно число — количество маршрутов.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
4 |
7 |
| |
|
Темы:
Динамическое программирование
Рекуррентные последовательности
Динамическое программирование: один параметр
Чтобы подготовиться к предстоящей битве 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.
| |
|
Темы:
Динамическое программирование
Рекуррентные последовательности
Числа Фибоначчи определяются рекуррентной формулой:
\(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 |
| |
|
Темы:
Динамическое программирование: один параметр
Рекуррентные последовательности
При переработке радиоактивных материалов образуются отходы двух типов: А (неопасные) и B (особо опасные). Отходы каждого типа упаковываются в контейнеры, а затем контейнеры складываются в стопки. Стопка считается взрывоопасной, если в ней есть три или больше контейнеров с особо опасными отходами (типа B ) расположены рядом. Для заданного количества контейнеров N определите, сколько есть способов составить безопасную стопку.
Входные данные
Входная строка содержит натуральное число – количество контейнеров N в стопке (1 <= N <= 35) .
Выходные данные
Программа должна вывести одно число – количество способов составить безопасную стопку из N контейнеров.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
3 |
7 |
| |
|
Темы:
Рекуррентные последовательности
У исполнителя Счетовод две команды, которым присвоены номера:
1. прибавь A
2. умножь на B
Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F ?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F .
Входные данные
Программа получает на вход четыре числа: A, B, S, F (1 <= A, B <= 10, 1 <= S <= 100, 1 <= F <= 103)
Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263 .
Примеры
№ |
Входные данные |
Выходные данные |
1 |
1
2
1
10 |
14 |
| |
|
Темы:
Рекуррентные последовательности
У исполнителя Счетовод три команды, которым присвоены номера:
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 - различные числа)
Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263 .
Примеры
№ |
Входные данные |
Выходные данные |
1 |
1
2
3
1
18 |
96 |
| |
|
Темы:
Рекуррентные последовательности
У исполнителя Счетовод три команды, которым присвоены номера:
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 .
Примеры
№ |
Входные данные |
Выходные данные |
1 |
1
2
3
1
12 |
225 |
| |
|
Темы:
Рекуррентные последовательности
У исполнителя Счетовод две команды, которым присвоены номера:
1. прибавь A
2. умножь на B
3. возведи в квадрат
Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F ?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F .
Входные данные
Программа получает на вход четыре числа: A, B, S, F (1 <= A, B <= 10, 1 <= S <= 100, 1 <= F <= 103)
Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263 .
Примеры
№ |
Входные данные |
Выходные данные |
1 |
1
2
2
38 |
266 |
| |
|
Темы:
Рекуррентные последовательности
У исполнителя Счетовод две команды, которым присвоены номера:
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 .
Примеры
№ |
Входные данные |
Выходные данные |
1 |
26
49 |
22 |
| |
|
Темы:
Рекуррентные последовательности
У исполнителя Счетовод две команды, которым присвоены номера:
1. прибавь 1
2. сделай четное
3. сделай нечетное
Первая из них увеличивает на 1 число на экране, вторая умножает это число на 2, третья переводит число x в число 2x + 1 . Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21.
Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F ?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F .
Входные данные
Программа получает на вход два числа: S, F (1 <= S <= 100, 1 <= F <= 103)
Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263 .
Примеры
№ |
Входные данные |
Выходные данные |
1 |
2
16 |
40 |
| |
|
Темы:
Рекуррентные последовательности
У исполнителя Счетовод две команды, которым присвоены номера:
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 <= 103, S <= num1 < num2 <= F). Каждое число вводится с новой строки.
Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263 .
Примеры
№ |
Входные данные |
Выходные данные |
1 |
1
2
2
3
13
9
11 |
68 |
| |
|
Темы:
Рекуррентные последовательности
У исполнителя Счетовод две команды, которым присвоены номера:
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 <= 103, S >= num1 > num2 >= F). Каждое число вводится с новой строки.
Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263 .
Примеры
№ |
Входные данные |
Выходные данные |
1 |
1
3
3
22
2
11
4 |
369 |
| |
|
Темы:
Рекуррентные последовательности
У исполнителя Счетовод две команды, которым присвоены номера:
1. прибавь A
2. умножь на B
3. умножь на С
Первая из них увеличивает на A число на экране, вторая умножает число на экране на B , третья умножает число на экране на С . Программа для Счетовода – это последовательность команд. Сколько существует таких программ, которые исходное число S преобразуют в число F и при этом траектория вычислений программы содержит число num и не содержит число misnum ?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F, B не равно C.
Входные данные
Программа получает на вход семь чисел в следующем порядке: A, B, C, S, F, num, misnum (1<= A,B,C <= 10, 1 <= S <= 100, 1 <= F <= 103, S <= num < misnum <= F). Каждое число вводится с новой строки.
Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263 .
Примеры
№ |
Входные данные |
Выходные данные |
1 |
1
2
3
3
46
12
25 |
369 |
| |
|
Темы:
Рекуррентные последовательности
Алгоритм вычисления функции 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). Каждое число в отдельной строке.
Выходные данные
Выведите ответ на задачу.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
3000
2000 |
2503500 |
| |
|
Темы:
Рекуррентные последовательности
Алгоритм вычисления функции 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). Каждое число в отдельной строке.
Выходные данные
Выведите ответ на задачу.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
3000
2000 |
1251000 |
| |
|
Темы:
Рекуррентные последовательности
Алгоритм вычисления функции 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). Каждое число в отдельной строке.
Выходные данные
Выведите ответ на задачу.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
2023
2007 |
32248 |
| |
|
Темы:
Рекуррентные последовательности
Рассмотрим неубывающую последовательность s1, ..., sn + 1 ( si <= si + 1 для 1 <= i <= n ). Последовательность m1, ..., mn, в которой каждый член определен как mi = ½ * ( si + si + 1 ) для 1 <= i <= n, назовем “средней последовательностью” для последовательности s1, ... sn + 1. Например, средняя последовательность для последовательности 1, 2, 2, 4 есть 1.5, 2, 3. Заметим, что элементы средней последовательности могут быть дробными числами. Тем не менее, в данной задаче используются только те средние последовательности, в которых все числа целые. Для заданной неубывающей последовательности из n целых чисел m1, ..., mn необходимо вычислить количество всех неубывающих последовательностей из n + 1 целых чисел s1, ..., sn + 1, для которых заданная последовательность m1, ..., mn является средней последовательностью.
Задание
Напишите программу, которая:
• читает из стандартного ввода неубывающую последовательность целых чисел;
• вычисляет количество всех неубывающих последовательностей целых чисел, для которых заданная последовательность является средней последовательностью;
• выводит ответ в стандартный вывод.
Входные данные
Первая строка стандартного ввода содержит одно целое число n (2 <= n <= 5000000). Оставшиеся n строк содержат значения последовательности m1, ..., mn. Строка i + 1 содержит одно целое число mi (0 <= mi <= 1000000000).
Выходные данные
Ваша программа должна вывести в стандартный вывод ровно одно целое число – количество всех неубывающих последовательностей целых чисел, для которых входная последовательность является средней последовательностью.
| |
|
Темы:
Рекуррентные последовательности
Последовательность чисел Фибоначчи определяется следующим образом: F0 = F1 = 1,
Fn+1 = Fn+Fn-1. Напишите программу для вычисления последней цифры n-го члена последовательности.
Входные данные
В единственной строке входных данных записано натуральное число n (1≤n≤1000).
Выходные данные
Вывести последнюю цифру числа Fn.
| |
|
Темы:
Рекуррентные последовательности
Вычислите n-й член последовательности, заданной формулами:
a2n = an + an-1,
a2n+1 = an – an-1,
a0 = a1 = 1.
Входные данные
Вводится одно натуральное число n (1≤n≤1000).
Выходные данные
Вывести одно число an.
| |
|
Темы:
Рекуррентные последовательности
Вычислите n-й член последовательности, заданной формулами:
a2n = an + 1 (n>0),
a2n+2 = a2n+1 - an (n>0),
a0=1, a1=1.
Входные данные
Вводится натуральное число n, не превосходящее 1000.
Выходные данные
Выведите ответ к задаче.
| |
|