Оборона підземелля#12994

Оборона підземелля (Розбір)

Припустимо, що ширина більша, ніж висота. Побудуємо одну захисну лінію, рухаючись вправо, поки це можливо, потім піднімемось угору на один крок і повторюватимемо це.

Позначимо точки, де відстань до лівого краю дорівнює відстані до нижнього краю. Між такими точками можна змінити горизонтальні та вертикальні лінії без порушення умов. Отже, кількість можливих ліній дорівнює , де — кількість таких проміжків.