Задача с СГУ
http://acm.sgu.ru/problem.php?contest=0&problem=225.
Суть задачи вкратце - сколько есть способов расставить на доске n*n k не бьющих друг друга лошадей. n и k до 10. Решается суд я по всему дп по профилю.
После нескольких часов попыток сдать эту задачу без прекалка, возник вопрос - а существует ли такое решение вообще? Может мы совместными усилиями его придумаем? Предлагаю помериться временем расчета на максимальном тесте .
http://acm.sgu.ru/problem.php?contest=0&problem=225.
Суть задачи вкратце - сколько есть способов расставить на доске n*n k не бьющих друг друга лошадей. n и k до 10. Решается суд я по всему дп по профилю.
После нескольких часов попыток сдать эту задачу без прекалка, возник вопрос - а существует ли такое решение вообще? Может мы совместными усилиями его придумаем? Предлагаю помериться временем расчета на максимальном тесте .
Т.е. если тупо влоб, то профилей 1024^2, а матрица переходов вообще 1024^3
Круто, стало быть это возможно.
А чей? Не Станкевича случайно? :)
делаем ставки, господа - запинаю в 0.5 или нет :D
продолжаем маразм :D
мое решение работает 2 секунды на моём пне 2.4 гц
на тимусе секунду. на сгу тл 122
ну, я тоже как сокобан заслал - 0.125. только, думаю, это сам компилятор так круто прооптимизировал, потому что n и k там получились константы.
только там черт ногу сломит :D если надо будет - потом комментарии допишу