Довольно простая задача на комбинаторику, позволяющая вспомнить формулы числа сочетаний и размещений. Читаем условие:
Вспомним, что ладья может ходить только по горизонтали и по вертикали. Это значит, что на каждой строке (и в каждом столбце) может стоять не больше одной ладьи.
Решать будем в два этапа. Сначала давайте зафиксируем строки, на которые поставим ладьи. Количество различных способов это сделать равно числу сочетаний из n по k (C(n, k)).
Как говорит Википедия:
В комбинаторике сочетанием из n по k называется набор из k элементов, выбранных из n-элементного множества, в котором не учитывается порядок элементов.
То есть то, что нам и надо. Формула тоже очень простая: n! / k! / (n - k)!
Но мы поступим ещё проще - будем использовать готовую функцию из модуля math:
math.comb(n, k)
Return the number of ways to choose k items from n items without repetition and without order.
Evaluates to n! / (k! * (n - k)!) when k <= n and evaluates to zero when k > n.
Дополнительным позитивным моментом является корректная обработка случая k > n ровно так, как требуется в задаче.
Вторым этапом надо выбрать столбцы для каждой из ладей. Так как две ладьи не могут стоять в одном столбце, то это это выбор без повторений. Или, в терминах комбинаторики, размещение без повторений (A(n, k)).
Формула ещё проще: n! / (n - k)!. Но, точно так же, уже есть готовая функция:
math.perm(n, k=None)
Return the number of ways to choose k items from n items without repetition and with order.
Evaluates to n! / (n - k)! when k <= n and evaluates to zero when k > n.
Ответом будет перемножение двух полученных значений, потому что это независимые выборы. То есть для каждого набора строк можно выбрать весь список наборов столбцов.
Теперь можем сразу написать решение:
Благодаря встроенным функциям и отсутствием проблем с большими числами мы получили очень красивое и понятное решение.
Предыдущий выпуск: Задача 127. Путь
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.