Гост написа:softuniada p8.png
On a rectangular chess board with X rows and Y columns, N rooks should be placed in such a way, so that each of them is attacked by at most 1 other rook. One rook is attacked by another rook, if they are placed on the same row, or on the same column, and there are no other rooks between them.
Write a program, which finds the count of all possible ways that these N rooks can be placed on the X / Y chess board, so that they cover the conditions specified above. Due to the fact, that the answer may be a very big number, always print the remainder of the division of the actual count with 1,000,001.
Input
The input consists of 3 input lines:
• On the first line you will receive X – the rows of the chessboard
• On the second line you will receive Y – the columns of the chessboard
• On the third line you will receive N – the count of rooks that should be placed on the chessboard
Output
The output should consist of a single line, containing the remainder of the division of the desired count, with 1,000,001.
Constraints
• X, Y and N will be integers in range [1, 100].
• Allowed working time / memory: to be defined.
Ако може решението да е на C#. Или ако не можете да решите цялата задача, поне дайте идеи за решение.
Това е много интересна задача и ми отне доста време докато обмислях различни решения, но и аз пък не бързах. В началото си мислех, че може би има директна формула която да даде резултата. Още не съм намерил такава. След това реших, че сигурно има хубава рекурсивна функция която в комбинация с Dynamic programming и @lru_cache ще свърши работа и такова наистина се оказа решението което представям тук.
Първо написах програма която по възможно най-brute force намира отговора за малките числа. няма да я давам тук, но сложноста и е нещо като $O(XY2^{XY})$. Най-големите стойности за които я пуснах бяха X=5, Y=5, N=7 и върна резултат след 30 секунди. Но ми даде тестови данни с които да тествам бързата функция.
Бързата функция е:
$f(x,y,n) = \frac{x(x-1)}{2}f(x-2,y-1,n-2) + f(x,y-1,n) + x(y-1)f(x-1,y-2,n-2) + xf(x-1,y-1,n-1)$
Как съставих тази функция? Идеята е следната, например първата част $\frac{x(x-1)}{2}f(x-2,y-1,n-2)$ казва слагаме един топ на първия ред на някоя $x$ позиция, слагаме 2-ри топ на същия ред на някоя от останалите $x-1$ позиции , умножаваме тези две числа и ги делим на 2 и това са броя на комбинациите които можем да направим от 2 топа на един ред и след това от дъската изключваме този ред и тези 2 колони, защото не можем на тях да слагаме повече топове и пускаме фунцкията за останалите $f(x-2,y-1,n-2)$. Останалите части подобна логика.
Програмата която я имплементира е:
- Код: Избери целия код
from functools import lru_cache
@lru_cache(maxsize = None)
def f(x,y,n):
if x<=0 or y<=0 or n==0:
return 0
if n == 1:
return x*y
if n == 2:
return x*y*(x*y-1)//2
return x*(x-1)*f(x-2,y-1,n-2)//2 + f(x,y-1,n) + x*(y-1)*f(x-1,y-2,n-2) + x*f(x-1,y-1,n-1)
Да я тестваме с примерите:
In [102]: f(4,6,2)
Out[102]: 276
In [103]: f(9,6,10)
Out[103]: 340200
In [104]: f(99,98,100)
Out[104]: 47716292659965237869320265557301253064912097095671321541359391563983349799122665140807253019080511522871444179307786903481024995730822967772318401645588881634937699689344614655096884769587200000000000000000000000
In [105]: f(99,98,100) % 1000001
Out[105]: 951454
Каква е сложността на бързата функция нямам представа, но малко експериментални данни до X=400, Y=400 приличат на $O(X^3)$
Меню