Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Ход конем

(Время: 1 сек. Память: 16 Мб Сложность: 53%)

Для решения этой задачи применим метод динамического программирования. Пусть b[d][k] – количество номеров, набираемых ходом коня, которые начинаются с цифры d и состоят из k цифр. Тогда b[d][1]=1 для всех d, а b[d][k] для любого d вычисляется через сумму b[i][k-1] для k>1. Так, например, b[4][k] = b[0][k-1]+b[3][k-1]+b[9][k-1]. Увеличивая k от 2 до n мы получим значения b[d][n], сумма которых (за вычетом b[0][n] и b[8][n]) и даст ответ на поставленную задачу.

Заметим также, что при вычислении могут получаться достаточно большие значения, поэтому следует применить длинную арифметику.


[Обсуждение] [Все попытки] [Задача]


Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483