만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

실현 가능한 반올림

면접 대비

시간 제한1초메모리 제한512 MB

요약
각 소수를 내림 또는 올림한 정수로 바꾸면서 모든 행 합과 열 합이 주어진 값과 일치하도록 하고, 그런 표 중 사전순으로 가장 앞선 것을 구한다.
난이도

어려움10점 중 8점

유형
그리디, 행렬, 구현, 수학
정답자
아직 제출이 없습니다

문제

박 교수는 매일 실험에서 얻은 데이터 NN개를 기록한다. 각 데이터 값은 소수점 첫째 자리까지의 실수로 적혀 있다. MM일 동안의 기록은 MM행 NN열 표로 정리되고, 표에는 각 행의 합과 각 열의 합도 함께 적혀 있다.

이 표를 논문에 실으려면 데이터 값과 행의 합과 열의 합이 모두 정수여야 한다. 표에 적힌 실수 xx는 ⌊x⌋\lfloor x \rfloor 또는 ⌈x⌉\lceil x \rceil로 바꿀 수 있다. 바꾼 뒤에 모든 행에서 데이터 값 NN개의 합이 그 행의 합과 같고, 모든 열에서 데이터 값 MM개의 합이 그 열의 합과 같으면, 새 표를 실현 가능한 반올림 표라고 한다.

원래 표가 주어지면 실현 가능한 반올림 표를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 MM과 NN이 주어진다. MM은 실험 일수이고 NN은 하루에 기록하는 데이터 개수이다 (2≤M≤2002 \le M \le 200, 2≤N≤2002 \le N \le 200).

다음 MM개의 줄에는 각각 실수가 N+1N+1개씩 주어진다. ii번째 줄의 앞쪽 NN개는 ii일째 데이터 값이고, 마지막 하나는 ii번째 행의 합이다. 그다음 줄에는 열의 합 NN개가 주어진다.

모든 실수는 소수점 첫째 자리까지 주어지고, 데이터 값은 0.00.0 이상 1000.01000.0 이하이다. 각 행의 합은 그 행 데이터 값의 합과 정확히 같고, 각 열의 합은 그 열 데이터 값의 합과 정확히 같다.

출력

M+1M+1개의 줄을 출력한다. ii번째 줄에는 ii일째 데이터 값 NN개를 정수로 바꾼 값과 ii번째 행의 합을 정수로 바꾼 값을 공백 하나로 구분해 출력한다. 마지막 줄에는 열의 합 NN개를 정수로 바꾼 값을 공백 하나로 구분해 출력한다.

실현 가능한 반올림 표는 여러 개일 수 있다. 출력하는 정수를 위에서 정한 순서대로 나열한 수열을 비교해서 사전순으로 가장 작은 표를 출력한다. 실현 가능한 반올림 표는 항상 존재한다.

예제3

  1. 예제 1

    입력
    3 3
    4.3 6.7 7.1 18.1
    9.2 3.0 0.2 12.4
    4.0 7.7 1.3 13.0
    17.5 17.4 8.6
    
    예상 출력
    4 6 8 18
    9 3 0 12
    4 8 1 13
    17 17 9
    
  2. 예제 2

    입력
    2 3
    0.4 0.4 0.4 1.2
    0.5 0.5 0.5 1.5
    0.9 0.9 0.9
    
    예상 출력
    0 0 1 1
    0 1 0 1
    0 1 1
    
  3. 예제 3

    입력
    2 2
    0.5 0.5 1.0
    0.5 0.5 1.0
    1.0 1.0
    
    예상 출력
    0 1 1
    1 0 1
    1 1