Темы --> Информатика --> Алгоритмы --> Динамическое программирование --> Динамическое программирование: два параметра --> Динамическое программирование: последовательности
---> 46 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 4 5 6 7 8 9 10 >> Отображать по:
#2998
Плавные числа
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Назовем число плавным, если его две соседние цифры различаются не более, чем на 1. По данному натуральному n определите количество плавных натуральных чисел, имеющих длину n. Гарантируется, что ответ не превосходит 231-1.

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

Вводится натуральное число n

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

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

Примеры
Входные данные
1
Выходные данные
9
Входные данные
2
Выходные данные
26
#2999
Ход коня
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-49-27. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.

Вид клавиатуры телефона:

123
456
789
 0 

Напишите программу, определяющую количество телефонных номеров длины N, набираемых ходом коня.

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

Программа получает на вход натуральное число N.

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

Программа должна вывести искомое количество телефонных номеров. Гарантируется, что ответ не превосходит 231-1.

Примеры
Входные данные
2
Выходные данные
16
#3000
Бросание кубика
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Кубик, грани которого помечены цифрами от 1 до 6, бросают N раз. Определите вероятность того, что сумма выпавших чисел будет в точности равна Q.

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

Программа получает на вход два целых числа: N и Q (1≤N≤500, 1≤Q≤3000).

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

Программа должна вывести единственное действительное число: искомую вероятность с точностью не менее чем 10-6.

Примечание

Искомая вероятность равна отношению числа последовательностей длины N, составленных из чисел от 1 до 6, дающих в сумме число Q, к числу всех таких последовательностей длины N.

Примеры
Входные данные
2 2
Выходные данные
0.0277778
Входные данные
2 12
Выходные данные
0.0277778
#3001
Пилообразные последовательности
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Назовем последовательность пилообразной, если каждый ее элемент либо строго больше, либо строго меньше своих соседей. По данными числам n и k определите число пилообразных последовательностей длины n, составленных из чисел 1..k.

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

Программа получает на вход два натуральных числа n и k, не превосходящих 106. Гарантируется, что ответ не превосходит 231-1.

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

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

Примеры
Входные данные
3 3
Выходные данные
10
#3002
Пилообразные последовательности - 2
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Назовем последовательность пилообразной, если каждый ее элемент либо строго больше, либо строго меньше своих соседей. По данными числам n и k определите число пилообразных последовательностей длины n, составленных из чисел 1..k.

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

Программа получает на вход два натуральных числа n и k,  1≤n≤1000, 1≤k≤1000.

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

Необходимо вывести остаток от деления количества искомых последовательностей на 109+7.

Примеры
Входные данные
3 3
Выходные данные
10
Входные данные
30 3
Выходные данные
4356618
Страница: << 4 5 6 7 8 9 10 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест