|
Название задачи: Ход конем . |
 |
Условие
Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-49-27. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.
| 7 | 8 | 9 |
| 4 | 5 | 6 |
| 1 | 2 | 3 |
| 0 |
Напишите программу, определяющую количество телефонных номеров
длины N, набираемых ходом коня.
Входные данные
Во входном файле записано целое число
N (1 ≤ N ≤ 100).
Выходные данные
Выведите в выходной файл искомое количество телефонных номеров.
Пример входного файла
2
Пример выходного файла
16
Решение
Скачать архив тестов и решений
Пусть F(k, d) означает количество набираемых ходом коня последовательностей
цифр длины k, первая из которых равна d. Выпишите рекуррентные
соотношения для чисел F(k, d). Например, F(k+1, 6) = F(k, 0)
+
F(k, 1)
+
F(k, 7). Ответом на задачу будет являться сумма чисел F(N, d), взятая по всем цифрам
d, отличным от 0 и 8.
