RooksPlacement
SRM 354 · 2007-06-14 · by Andrew_Lazarev
Problem Statement
You will be given three integers N, M and K. You are to calculate the number of ways to place K rooks on a NxM chessboard in such a way that no rook is attacked by more than one other rook. A rook is attacked by another rook if they share a row or a column and there are no other rooks between them. To avoid problems with big numbers the calculation should be done modulo 1,000,001.
Constraints
- N will be between 1 and 50, inclusive.
- M will be between 1 and 50, inclusive.
- K will be between 1 and 100, inclusive.
4 5 2 Returns: 190
There are only two rooks and therefore all placements are valid. The number of placements is (4 * 5) * (4 * 5 - 1) / 2 = 190.
2 3 3 Returns: 6
There are 6 possible placements: XX. X.X .XX ..X .X. X.. ..X .X. X.. XX. X.X .XX
6 7 20 Returns: 0
50 25 50 Returns: 879507
9 6 10 Returns: 340200
Submissions are judged against all 116 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RooksPlacement with a public method int countPlacements(int N, int M, int K) · 116 test cases · 2 s / 256 MB per case