빠진 숫자
면접 대비시간 제한2초메모리 제한512 MB
행 합계와 열 합계는 그대로 있고 일부 칸만 지워진 판매 표가 주어질 때, 빠진 값을 유일하게 정할 수 있는지 판정하고 등장 순서대로 출력하며, 유일하지 않으면 NO를 출력한다.
문제
Toshizo는 하코다테에서 편의점 체인을 운영하는 지배인이다. 매일 체인의 각 점포는 그날 판매한 상품 표를 그에게 보낸다. Toshizo의 일은 이 수치를 모아 점포들이 모두 합쳐 얼마나 팔았는지 계산하는 것이다.
점포가 Toshizo에게 보내는 표는 다음과 같은 모양이다(모든 숫자는 판매한 상품의 개수이다).
Store1 Store2 Store3 Totals
Product A -5 40 70 | 105
Product B 20 50 80 | 150
Product C 30 60 90 | 180
-----------------------------------------------------------
Store's total sales 45 150 240 435
표를 보면 Toshizo는 어떤 상품이 잘 팔리고 어떤 상품이 안 팔리는지, 어떤 점포가 실적이 좋고 어떤 점포가 너무 비어 있는지 한눈에 알 수 있다. 손님이 상품을 반품하는 경우도 있어서 표의 숫자는 양수일 수도 있고 음수일 수도 있다.
Toshizo는 이 수치를 도쿄에 있는 상사에게 보고하고, 둘은 함께 실적이 나쁜 점포를 닫기로 결정하기도 하고 수익이 날 것 같은 곳에 새 점포를 열기로 결정하기도 한다. 따라서 Toshizo가 관리하는 점포의 총수는 고정되어 있지 않다. 또한 인기가 없는 일부 상품의 판매를 중단하기로 결정하는 한편 인기가 있을 것 같은 새 상품을 들여놓기로 결정하기도 한다. 따라서 Toshizo가 살펴야 하는 상품의 수도 고정되어 있지 않다.
어느 새해, 하코다테는 매우 춥다. Toshizo의 사무실에서 수도관이 터져 그의 책상을 물에 잠기게 한다. 출근한 Toshizo는 최신 판매 표를 읽을 수 없다는 것을 발견한다. 일부 숫자는 알아볼 수 있지만 전부는 아니다. 그는 도쿄의 상사에게 전화해 수치가 늦어진다고 말하고 싶지만, 상사가 가능하다면 표를 복원해 오기를 기대한다는 것을 안다.
다음 날까지 기다려도 소용없다. 새해라서 그의 점포가 휴업하기 때문이다. 그래서 Toshizo는 값을 직접 알아내거나, 정말로 유일한 해가 없다는 것을 확신하기로 한다. 그래야만 상사에게 전화해 무슨 일이 있었는지 말할 수 있다.
그러나 Toshizo는 이런 문제가 다시는 일어나지 않기를 바란다. 그래서 그는 회사의 모든 지배인이 판매 표에서 일부 데이터가 사라졌을 때 사용할 수 있는 컴퓨터 프로그램을 작성하기로 한다. 예를 들어 그들이 다음과 같은 표를 가지고 있다면:
Store 1 Store 2 Store 3 Totals
Product A ? ? 70 | 105
Product B ? 50 ? | 150
Product C 30 60 90 | 180
--------------------------------------------------------
Store's total sales 45 150 240 435
Toshizo의 프로그램은 물음표를 대신할 올바른 값을 그들에게 알려 줄 수 있다. 그러나 어떤 경우에는 그의 프로그램도 일반적으로 모든 물음표를 대체할 수 없다. 예를 들어 다음과 같은 표가 주어지면:
Store 1 Store 2 Totals
Product A ? ? | 40
Product B ? ? | 40
---------------------------------------------
Store's total sales 40 40 80
가능한 해가 무한히 많다. 이런 경우 그의 프로그램은 그냥 "NO"라고 말한다. Toshizo의 프로그램은 합계 행과 열이 그대로 남아 있는 모든 데이터에 대해 작동한다. Toshizo의 프로그램을 재현할 수 있는가?
입력
입력은 여러 개의 데이터 세트로 이루어지며, 각각은 다음 형식이다.
p s
row1
row2
...
rowp
totals
첫 줄은 두 정수 p와 s로, 각각 상품의 수와 점포의 수를 나타낸다. 전자는 100 미만이고 후자는 10 미만이다.
두 수는 공백 문자로 구분된다. 그다음 각 줄은 표의 한 행을 나타내며 s+1개의 원소로 이루어지고, 각 원소는 정수이거나 물음표이다. i번째 줄(1 <= i <= p)은 i번째 상품에 대응하고 마지막 줄은 합계 행이다. 한 줄에서 처음 s개의 원소는 각 점포의 판매량을 나타내고 마지막 원소는 그 상품의 총 판매량을 나타낸다. 한 줄에서 숫자나 물음표는 공백 문자로 구분된다. 합계 열과 합계 행에는 빠진 숫자가 없다. 각 데이터 세트에는 물음표가 적어도 하나 있다.
합계 행과 열을 제외하고 표에서 알려진 숫자는 -1,000 이상 1,000 이하이다. 그러나 물음표로 나타나는 알려지지 않은 숫자는 이 범위를 벗어날 수 있다. 각 상품의 총 판매량은 -10,000 이상 10,000 이하이다. 각 점포의 총 판매량은 -100,000 이상 100,000 이하이다.
입력에서 각 데이터 세트 사이에는 빈 줄이 있고, 입력은 0 하나로 이루어진 줄로 끝난다.
출력
유일한 해가 있으면 프로그램은 입력 데이터 세트에서 나타난 순서대로 빠진 숫자를 출력해야 한다. 그렇지 않으면 프로그램은 "NO"만 출력해야 한다. 연속된 데이터 세트의 답은 빈 줄로 구분한다. 비어 있지 않은 각 출력 줄에는 숫자 하나 또는 "NO"만 들어 있다.