Путешествие по доске

[Ktina]

На доске $10\times 10$ отмечены клетки

$$b7,\quad c6,\quad d5,\quad e4,\quad f3,\quad f6,\quad f10,\quad g2,\quad g8,\quad h7\quad\text{и}\quad j6.\quad $$

Сколькими способами можно из клетки $a1$ попасть в $j10$, двигаясь только по неотмеченным клеткам вверх или вправо?

[denisart]

(Оффтоп)

48?

[Ktina]

denisart в сообщении #750137 писал(а):

(Оффтоп)

48?

Вот у меня столько же получилось, но олимпиадного решения я не нашла. Как, впрочем, и здесь.

[nikvic]

Ktina в сообщении #750139 писал(а):

Вот у меня столько же получилось, но олимпиадного решения я не нашла. Как, впрочем, и здесь.

Ну, алгоритм-то описан...

[Ktina]

nikvic в сообщении #750140 писал(а):

Ktina в сообщении #750139 писал(а):

Вот у меня столько же получилось, но олимпиадного решения я не нашла. Как, впрочем, и здесь.

Ну, алгоритм-то описан...

Он неолимпиаден! Просто бестолковый подсчёт.

-- 29.07.2013, 12:31 --

А если доска будет $69\times 69$? Сколько часов займёт выполнение этого алгоритма?

[nikvic]

Ktina в сообщении #750142 писал(а):

Он неолимпиаден! Просто бестолковый подсчёт.

Описан классический алгоритм для задач из "динамического программирования", линейный по времени. До него нужно догадаться - чтобы избежать перебора.
Т.к. с арифметикой проблемы, условия ориентированы на сложение маленьких чисел

[Ktina]

nikvic в сообщении #750146 писал(а):

Описан классический алгоритм для задач из "динамического программирования", линейный по времени. До него нужно догадаться - чтобы избежать перебора.
...

До него не нужно догадываться, эту задачу ещё в четвёртом классе дают.

[nikvic]

Ktina в сообщении #750148 писал(а):

До него не нужно догадываться, эту задачу ещё в четвёртом классе дают.

В каждой олимпиаде должна быть утешительная задача

Просмотрел ссылку для 4-го класса - аналога не нашёл. Который номер?