Round each decimal entry to floor or ceiling so that every row and column sum still matches its stated total, choosing the lexicographically smallest whole table.
Hard8GreedyMatrixImplementationMathInterviewNo attempts yetTime limit1sMemory limit512 MBProfessor Park records the N data values of his experiment every day. Each value is written as a real number with one digit after the decimal point. The records of M days form a table with M rows and N columns, and the table also carries the sum of each row and the sum of each column.
To publish the table, the data values, the row sums, and the column sums must all be integers. A real number x written in the table can be replaced by ⌊x⌋ or ⌈x⌉. If, after the replacement, the N data values of every row add up to that row's sum and the M data values of every column add up to that column's sum, the new table is called a feasibly rounded table.
Given the original table, write a program that finds a feasibly rounded table.
The first line contains two integers M and N. M is the number of experiment days and N is the number of data values recorded each day (2≤M≤200, 2≤N≤200).
Each of the next M lines contains N+1 real numbers. The first N numbers on the i-th line are the data values of day i, and the last one is the i-th row sum. The next line contains the N column sums.
Every real number is given with one digit after the decimal point, and every data value is between 0.0 and 1000.0, inclusive. Each row sum is exactly the sum of the data values in that row, and each column sum is exactly the sum of the data values in that column.
Print M+1 lines. On the i-th line, print the N rounded data values of day i and then the rounded i-th row sum, separated by single spaces. On the last line, print the N rounded column sums separated by single spaces.
More than one feasibly rounded table can exist. Compare tables by the sequence of the integers you print, in the order above, and print the lexicographically smallest one. A feasibly rounded table always exists.