ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 102781
Темы:    [ Динамическое программирование (прочее) ]
[ Длинная арифметика как инструмент ]
Сложность: 3
Классы:
Название задачи: Ход конем .
В корзину
Прислать комментарий

Условие

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

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .