SumOfSelectedCells
SRM 360 · 2007-07-24 · by darnley
Problem Statement
There is a rectangular table with an integer written in each cell.
Later, Jessie will come and select some cells in such a way that each row and each column contains no more than one selected cell. She will always select the maximum possible number of cells. However, there might be several possible selections of that size.
Larry suggested a hypothesis: "No matter what maximum selection Jessie choses, the sum of the numbers in the selected cells will always be the same."
Given a
Constraints
- table will contain between 1 and 20 elements, inclusive.
- Each element of table will be contain between 1 and 50 characters, inclusive.
- Each element of table will be a space-separated list of integers.
- Each element of table will contain the same number of entries.
- Each element of table will contain between 1 and 20 entries, inclusive.
- All numbers in the table will be between 1 and 50, inclusive, with no leading zeroes.
{"5 6 6"}
Returns: "INCORRECT"
Jessie will select exactly one cell. The sum will be either 5 or 6.
{"11 12 13 14",
"21 22 23 24",
"31 32 33 34",
"41 42 43 44"}
Returns: "CORRECT"
There are 4! = 24 possible selections for Jessie, but it can be shown that each of them gives the sum of 1 + 2 + 3 + 4 + 10 + 20 + 30 + 40 = 110.
{"3 7",
"3 7",
"3 7"}
Returns: "CORRECT"
Jessie will select exactly one 3 and exactly one 7 giving a total of 10.
{"1 2 3",
"4 5 6",
"9 8 7"}
Returns: "INCORRECT"
Jessie can get 13 (2 + 4 + 7) or 15 (1 + 6 + 8) or 17 (3 + 5 + 9).
{"1"}
Returns: "CORRECT"
Submissions are judged against all 192 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SumOfSelectedCells with a public method string hypothesis(vector<string> table) · 192 test cases · 2 s / 256 MB per case