All submissions for this problem are available.
Mr. Devu Singh has a farm. The farm is represented as a matrix, divided into rows and columns, with each element being equal to 1, if the corresponding area in the farm contains a tree, and 0 otherwise. Every element in the farm can contain atmost one tree.
Mr. Devu Singh loves his farm. However, Devu Singh has a short memory. He cannot remember which of the elements in the farm has a tree in them. What he does remember is the total number of trees in each row and each column, but is not sure about this information either. He wishes to know, that for such constraints, whether there exists a matrix satisfying these constraints. If there does exist such a matrix, output the lexicographically smallest one, otherwise output -1.
For lexicographically comparing two matrices A and B, you write the matrix A and B as a string of 0/1 by writing in row major order (ie, first write first row, then second row and so on upto n-th row.). Now lexicographically compare the two strings generated in this way.
First line contains T : number of test cases.
For each test case, first line has N and M.
Next line contains N space separated integers where i-th one represents sum of the i-th row.
Line after that contains M space separated integers where i-th one represents sum of i-th column.
For the i-th test case, the first line contains the string "TestCase #:i" (without quotes). From the next line, output matrix of size N x M, as N lines containing M integers each (without space), with Element[i,j] = 0 or 1, depending on whether there can be a tree in that area. Output -1, if no such matrix exists.
- 1 ≤ T ≤ 20
- 1 ≤ N, M ≤ 50
- 0 ≤ Sum of elements in a row ≤ M
- 0 ≤ Sum of elements in a column ≤ N
3 2 3 1
4 3 1 1
1 3 0 2
1 1 2 2
For first test case, the given matrix is the lexicographically smallest one with sum of row1 =3,
sum of row2 =2, sum of row3 =3, sum of row4 =1 and sum of column1 =4, sum of column2 =3, sum of column3 =1, sum of column4 =1.
Similarly for the second test case, the given matrix is the lexicographically smallest one satisfying the given constraints.
For the third test case, there cannot be any matrix of size 1x1 and sum of row1=1 and sum of column1=0. Hence output is -1.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP 4.9.2, GO, JAVA|
Fetching successful submissions