Входной файл: input.txt Выходной файл: output.txt Время на тест: 1 секунда Ограничение на память: 16 MB Авторское решение:Pascal Тесты к задаче:Скачать
Недавно у Дмитрия Раисовича Хусаинова был день рождения. Его друг подарил ему мобильный телефон и предложил выбрать номер. Дмитрий Раисович выбрал номер 183492760 (не надо спрашивать у автора, почему он выбрал именно этот номер, спросите об этом у самого Дмитрия Раисовича). Посмотрите на расположение цифр на телефоне Дмитрия Раисовича:
1
2
3
4
5
6
7
8
9
0
Дмитрий Раисович, наверное, сам не подозревал, что он выбрал замечательный номер. Если набирать этот номер на телефоне, то, рассматривая клетки с цифрами как клетки на шахматной доске, каждая следующая цифра получается из предыдущей с помощью одного хода шахматного коня. Назовем такие номера шахматными. Теперь Дмитрия Раисовича очень интересует вопрос: сколько существует шахматных номеров из N цифр? К сожалению, недавно он решил слишком много задач на рекуррентные соотношения, и, вряд ли, сможет решить еще одну - он слишком устал. Так что решать эту задачу придется вам.
Задание.
По введенному числу N определите количество C шахматных номеров из N цифр. Примите во внимание, что телефонные номера не могут начинаться с нуля. Никаких других ограничений на цифры в телефонном номере нет.