NewMagicSquare

SRM 351 · 2007-05-29 · by Andrew_Lazarev

SRM 351 · 2007-05-29 · by Andrew_Lazarev · Math

Show categories

Class Name: NewMagicSquare

Return Type: String[]

Method Name: completeTheSquare

Arg Types: (vector<string>)

Problem Statement

You are to populate a 5x5 square with each of the numbers between 1 and 25, inclusive. The numbers in each row must be in increasing order from left to right. Some of the cells are already filled in, but no more than one number per row. You must fill in the remaining cells.

You will be given a String[] square. Each row is given as a space-separated list of cells. Each cell is either a number written with two digits (numbers less than 10 have an additional leading zero) or two '?' characters which represent an empty cell. Your method should return a String[] in the same format, but with all the empty cells filled in. If there are no arrangements possible return an empty String[]. If there are several arrangements possible return the one with the smallest first number in the first row. If there are still several arrangements possible return the one with the smallest second number in the first row, and so on.

Constraints

square will contain exactly 5 elements.
Each element of square will contain exactly 14 characters.
Each element of square will be a space-separated list of cells.
Each cell will be either a number written with two digits or two '?' characters.
Each element of square will contain at most one filled cell.
All numbers in square will be between 1 and 25, inclusive.
All numbers in square will be distinct.

Examples

{"?? ?? ?? ?? ??", 
 "?? ?? ?? ?? ??", 
 "?? ?? ?? ?? ??", 
 "?? ?? ?? ?? ??", 
 "?? ?? ?? ?? ??"}
Returns: {"01 02 03 04 05", "06 07 08 09 10", "11 12 13 14 15", "16 17 18 19 20", "21 22 23 24 25" }

You are not limited by prefilled cells. The answer is the lexicographically smallest square.

{"?? ?? 20 ?? ??", 
 "?? ?? ?? ?? ??", 
 "?? ?? ?? 05 ??", 
 "?? ?? ?? ?? ??", 
 "?? ?? ?? ?? ??"}
Returns: {"01 06 20 21 22", "07 08 09 10 11", "02 03 04 05 12", "13 14 15 16 17", "18 19 23 24 25" }

{"?? ?? ?? ?? ??", 
 "?? ?? ?? ?? 24", 
 "?? ?? ?? ?? ??", 
 "?? ?? ?? ?? ??", 
 "21 ?? ?? ?? ??"}
Returns: { }

You should place four numbers greater than 21 into the 5th row. There are four such numbers - 22, 23, 24 and 25, but 24 is already used in the second row.

{"?? ?? 15 ?? ??", 
 "02 ?? ?? ?? ??", 
 "?? ?? ?? 07 ??", 
 "?? ?? 16 ?? ??", 
 "?? ?? ?? ?? 21"}
Returns: {"01 03 15 17 18", "02 08 09 10 22", "04 05 06 07 23", "11 12 16 24 25", "13 14 19 20 21" }

{"?? ?? ?? ?? ??","?? ?? ?? ?? 12","?? ?? ?? 22 ??","?? ?? 21 ?? ??","?? ?? ?? ?? ??"}
Returns: {"01 02 03 04 05", "06 07 08 09 12", "10 11 13 22 23", "14 15 21 24 25", "16 17 18 19 20" }

Submissions are judged against all 55 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class NewMagicSquare with a public method vector<string> completeTheSquare(vector<string> square) · 55 test cases · 2 s / 256 MB per case