페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8260
서브태스크

테이블 복구 1초 1024MB

문제

Bessie는 N \times N (1 \leq N \leq 1000) 크기의 덧셈 테이블을 가지고 있다. 이 테이블에서 행 r, 열 c 에 위치한 셀의 값은 항상 r + c 이다. 예를 들어, N = 3 일 때 테이블은 다음과 같다.

\begin{array}{ccc} 2 & 3 & 4 \\ 3 & 4 & 5 \\ 4 & 5 & 6 \end{array}

하지만 Elsie가 이 테이블을 변형시켰다! 그녀는 다음과 같은 세 종류의 연산을 원하는 만큼 수행할 수 있다.

  1. 두 개의 행을 교환할 수 있다.

  2. 두 개의 열을 교환할 수 있다.

  3. 두 개의 값 a 와 b 를 선택한 후, 테이블에 등장하는 모든 a 를 b 로, 모든 b 를 a 로 동시에 바꿀 수 있다.

Elsie는 항상 연산을 위의 순서대로 수행한다. 즉,

  • 먼저 1번 연산(행 교환) 을 원하는 만큼 수행한 후,

  • 그다음 2번 연산(열 교환) 을 원하는 만큼 수행하고,

  • 마지막으로 3번 연산(값 교환) 을 수행한다.

우리는 Elsie가 1번과 2번 연산을 모두 끝낸 후, 3번 연산을 수행하기 직전의 상태를 복구해야 한다.

가능한 답이 여러 개일 경우, 사전순으로 가장 작은 테이블을 출력해야 한다.

  • 사전순 비교는 위에서 아래로, 왼쪽에서 오른쪽으로 읽을 때 첫 번째로 다른 값이 작은 테이블이 더 앞선다.


입력

첫 번째 줄에는 정수 N 이 주어진다.

다음 N 줄에는 N 개의 정수가 주어지며, Elsie가 변형한 덧셈 테이블이 제공된다.


출력

Elsie가 1번과 2번 연산만 수행한 후의 테이블 중, 사전순으로 가장 작은 상태의 테이블을 출력한다.

항상 해가 존재함이 보장된다.


부분문제

번호 점수 조건
#110점

N\le6

#220점

N\le8

#330점

N\le100

#440점

추가 제약 조건 없음


예제1

입력
1
2
출력
2

예제2

입력
3
342
523
635
출력
423
534
645
2 3 4
3 4 5
4 5 6
-> (op 1: swap columns 2 and 3)
2 4 3
3 5 4
4 6 5
-> (op 1: swap columns 1 and 2)
4 2 3
5 3 4
6 4 5
-> (op 3: swap values 2 and 3)
4 3 2
5 2 4
6 4 5
-> (op 3: swap values 3 and 4)
3 4 2
5 2 3
6 3 5

예제3

입력
6
8105674
121110482
546798
10248512
687935
41285610
출력
7589106
425673
86910117
536784
971011128
647895

출처

USACO 2025 January Silver

역링크