Задача 102781

Темы:    [ Динамическое программирование (прочее) ] [ Длинная арифметика как инструмент ]

Сложность: 3 Классы: Название задачи: Ход конем .

Условие

Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон [phone]. При этом телефонный номер не может начинаться ни с цифры 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.

Источники и прецеденты использования

книга
предмет	информатика
Автор	Беров В., Лапунов А., Матюхин В., Пономарев А.
Название	Особенности национальных задач по информатике
Издательство	Триада-С
Год издания	2000
глава
Номер	1
Название	Динамическое программирование
Задача
Номер	4