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