TaroCheckers
SRM 613 · 2013-12-22 · by Witaliy
Problem Statement
Cat Taro has a board with N rows and M columns divided into unit cells. He wants to place some checkers on the board. Each cell can contain at most one checker. The following conditions must be fulfilled:
- For each row i, there is exactly one cell with a checker among the first left[i] cells of the i-th row.
- For each row i, there is exactly one cell with a checker among the last right[i] cells of the i-th row.
- For each column, there is at most one cell with a checker in that column.
You are given the
Constraints
- left will contain between 1 and 50 elements, inclusive.
- right and left will contain the same number of elements.
- M will be between 2 and 200, inclusive.
- Each element of left and right will be between 1 and M, inclusive.
- For each valid i, the value left[i]+right[i] will be less than or equal to M.
{1, 2}
{2, 1}
4
Returns: 1
Only one way to place checkers is possible in this case: (In each row, the first left[i] and the last right[i] cells have a darker background.)
{1, 4, 2}
{2, 3, 1}
7
Returns: 6
{4, 7, 4}
{7, 4, 7}
11
Returns: 5760
{10, 25, 100, 74}
{100, 47, 27, 100}
200
Returns: 796178974
{53, 3, 1, 19, 6, 15, 2, 48, 1, 25, 28, 47, 17, 2, 11, 38, 33, 30, 28, 22, 18, 3, 7, 9, 9, 6, 3, 40, 9, 36, 3, 51, 3, 41, 16, 20, 21, 16, 15, 20, 19, 9}
{6, 5, 14, 16, 2, 29, 34, 18, 1, 21, 15, 2, 39, 1, 51, 16, 3, 8, 6, 40, 9, 5, 17, 27, 13, 41, 21, 10, 3, 25, 44, 2, 2, 8, 11, 3, 22, 7, 5, 4, 38, 4}
69
Returns: 0
Submissions are judged against all 63 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TaroCheckers with a public method int getNumber(vector<int> left, vector<int> right, int M) · 63 test cases · 2 s / 256 MB per case