Задача 5 - Карточки для счета (100 баллов)
| Полный балл: | 100 |
| Ограничение времени: | 1 с |
| Ограничение памяти: | 128M |
Юный программист Петя обучает своего младшего брата арифметике. Петя заготовил много карточек, на каждой из которых написана одна из цифр от 0 до 9 включительно. Петя решил что будет выкладывать карточки в ряд, а младший брат будет просматривать карточки слева направо, складывать цифры на двух соседних карточках и называть ответ. Например, если бы Петя выложил такую последовательность карточек: 2 3 4 1 2, то брат должен был бы назвать вот такую последовательность ответов: 5, 7, 5, 3.
Хотя Петя и любит арифметику, он все же решил сильно не нагружать брата, и выкладывать такие последовательности карточек, чтобы сумма на любых двух соседних карточках не превосходила некоторое число S. С другой стороны, Петя волнуется, а не слишком ли мало заданий получится для брата?
Напишите программу, которая посчитает количество различных последовательностей длины N, состоящих из цифр от 0 до 9 таких, что сумма двух соседних цифр в последовательности не превышает заданного числа S.
Формат входных данных
Ввод содержит два числа N (2 ≤ N ≤ 100) и S (0 ≤ S ≤ 18), разделенные пробелом - количество цифр в последовательности, и максимально возможное значение суммы двух соседних цифр в последовательности.
Формат результата
Выведите единственное число - количество различных последовательностей из цифр длины N, в которых сумма любых двух соседних цифр не превосходит S.
|
|
|
Примеры
Входные данные
3 1
Результат работы
5
Входные данные
3 2
Результат работы
14
Примечания
Последовательностей длины 3 таких, что сумма соседних элементов не превосходит 1, всего 5:
0 0 0
0 0 1
0 1 0
1 0 0
1 0 1
Дата добавления: 2018-11-24; просмотров: 214; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!