각 소수를 내림 또는 올림한 정수로 바꾸면서 모든 행 합과 열 합이 주어진 값과 일치하도록 하고, 그런 표 중 사전순으로 가장 앞선 것을 구한다.
어려움8그리디행렬구현수학면접 대비아직 제출이 없습니다시간 제한1초메모리 제한512 MB박 교수는 매일 실험에서 얻은 데이터 N개를 기록한다. 각 데이터 값은 소수점 첫째 자리까지의 실수로 적혀 있다. M일 동안의 기록은 M행 N열 표로 정리되고, 표에는 각 행의 합과 각 열의 합도 함께 적혀 있다.
이 표를 논문에 실으려면 데이터 값과 행의 합과 열의 합이 모두 정수여야 한다. 표에 적힌 실수 x는 ⌊x⌋ 또는 ⌈x⌉로 바꿀 수 있다. 바꾼 뒤에 모든 행에서 데이터 값 N개의 합이 그 행의 합과 같고, 모든 열에서 데이터 값 M개의 합이 그 열의 합과 같으면, 새 표를 실현 가능한 반올림 표라고 한다.
원래 표가 주어지면 실현 가능한 반올림 표를 구하는 프로그램을 작성하시오.
첫째 줄에 정수 M과 N이 주어진다. M은 실험 일수이고 N은 하루에 기록하는 데이터 개수이다 (2≤M≤200, 2≤N≤200).
다음 M개의 줄에는 각각 실수가 N+1개씩 주어진다. i번째 줄의 앞쪽 N개는 i일째 데이터 값이고, 마지막 하나는 i번째 행의 합이다. 그다음 줄에는 열의 합 N개가 주어진다.
모든 실수는 소수점 첫째 자리까지 주어지고, 데이터 값은 0.0 이상 1000.0 이하이다. 각 행의 합은 그 행 데이터 값의 합과 정확히 같고, 각 열의 합은 그 열 데이터 값의 합과 정확히 같다.
M+1개의 줄을 출력한다. i번째 줄에는 i일째 데이터 값 N개를 정수로 바꾼 값과 i번째 행의 합을 정수로 바꾼 값을 공백 하나로 구분해 출력한다. 마지막 줄에는 열의 합 N개를 정수로 바꾼 값을 공백 하나로 구분해 출력한다.
실현 가능한 반올림 표는 여러 개일 수 있다. 출력하는 정수를 위에서 정한 순서대로 나열한 수열을 비교해서 사전순으로 가장 작은 표를 출력한다. 실현 가능한 반올림 표는 항상 존재한다.