Анфіса і квіти#458

Анфіса і квіти (Editorial)

Розберемося, що обмежує кількість прогулянок.

Кожен маршрут веде з лівого верхнього кута в правий нижній, і за прогулянку Анфіса збирає квіти з усіх клітинок свого маршруту. Щоб отримати шматочок сиру, під час прогулянки вона має зібрати хоча б одну квітку, тобто кожен наступний маршрут повинен проходити щонайменше через одну клітинку, де квітка ще залишилась.

Перший маршрут проходить рівно через клітинку — стільки клітинок містить будь-який шлях з кута в кут. Після нього залишається nm - (n + m - 1) клітинок з квітами.

Оскільки кожна наступна прогулянка «витрачає» щонайменше одну нову клітинку, більше ніж

1 + \bigl(nm - (n + m - 1)\bigr) = nm - n - m + 2

прогулянок бути не може. Цю межу можна досягти: щоразу вибираючи маршрут, який зачіпає рівно одну ще не відвідану клітинку, Анфіса витрачає квіти якомога повільніше.

Отже, відповідь дорівнює nm - n - m + 2, що зручно записати як (n-1)(m-1) + 1.

Перевірте окремий випадок n = 1 або m = 1: тоді маршрут єдиний, і формула дає рівно .