레이팅 미적용베시는 \(N\times N\)(\(1\le N\le 1000\)) 덧셈표를 가지고 있다. 모든 \(1\le r,c\le N\)에 대해 행 \(r\), 열 \(c\)에 있는 칸의 정수는 \(r+c\)이다. 예를 들어 \(N=3\)일 때 표는 다음과 같다.
2 3 4
3 4 5
4 5 6
안타깝게도 엘시가 표를 손에 넣어 다음 세 종류의 연산을 원하는 만큼 수행하여 표를 뒤섞어 버렸다.
- 두 행을 교환한다
- 두 열을 교환한다
- 표에 모두 존재하는 두 값 \(a\)와 \(b\)를 선택한 뒤, 모든 \(a\)를 \(b\)로, 모든 \(b\)를 \(a\)로 동시에 바꾼다.
엘시는 항상 연산을 종류의 오름차순으로 수행한다. 즉, 먼저 종류 \(1\)의 연산을 원하는 만큼(없을 수도 있음) 수행하고, 그다음 종류 \(2\), 마지막으로 종류 \(3\)의 연산을 수행한다.
엘시가 종류 \(1\)과 \(2\)의 모든 연산을 마친 뒤, 종류 \(3\)의 연산을 하나라도 적용하기 전의 표로 가능한 상태 하나를 복원하도록 베시를 도와주자. 가능한 답이 여러 개일 수 있으며, 그 경우 사전순으로 가장 작은 것을 출력해야 한다.
두 표를 사전순으로 비교할 때는, 두 표를 자연스러운 순서(행은 위에서 아래로, 한 행 안에서는 왼쪽에서 오른쪽으로)로 읽으면서 처음으로 달라지는 항목을 비교한다.
Problem credits: Benjamin Qi
배점
- 입력 4-5: \(N\le 6\)
- 입력 6-7: \(N\le 8\)
- 입력 8-11: \(N\le 100\)
- 입력 12-15: 추가 제약이 없다.
Problem credits: Benjamin Qi
첫째 줄에 \(N\)이 주어진다.
다음 \(N\)개의 줄에 각각 \(N\)개의 정수가 주어지며, 이는 엘시가 뒤섞은 후의 베시의 덧셈표를 나타낸다.
종류 1과 2의 모든 연산이 끝난 뒤, 종류 3의 연산이 적용되기 전의 표로 가능한 상태 중 사전순으로 가장 작은 것을 출력한다. 답이 존재함이 보장된다.
1
22Regardless of what operations Elsie performs, the table won't change.
3
3 4 2
5 2 3
6 3 54 2 3
5 3 4
6 4 5Here is a possible sequence of operations Elsie might have performed.
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
Note: the following is also a possible state of the table after operations of
types 1 and 2, but it is not the lexicographically smallest because the second
entry of the first row is larger than in the correct answer.
4 6 5
3 5 4
2 4 3
6
8 10 5 6 7 4
12 11 10 4 8 2
5 4 6 7 9 8
10 2 4 8 5 12
6 8 7 9 3 5
4 12 8 5 6 107 5 8 9 10 6
4 2 5 6 7 3
8 6 9 10 11 7
5 3 6 7 8 4
9 7 10 11 12 8
6 4 7 8 9 5riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > January > Silver