레이팅 미적용농부 존에게는 \(1\ldots N\)으로 번호가 붙은 \(N\)개의 선물이 있고, 마찬가지로 \(1\ldots N\)으로 번호가 붙은 \(N\) (\(1\le N\le 500\))마리의 소들이 있다. 각 소에게는 위시리스트가 있는데, 이는 \(N\)개의 선물 전체에 대한 순열로, 소는 목록에서 앞에 나오는 선물을 뒤에 나오는 선물보다 선호한다.
FJ는 게을러서 모든 \(i\)에 대해 그냥 선물 \(i\)를 소 \(i\)에게 배정했다. 이제 소들이 모여서 선물을 재배정하기로 했는데, 재배정 후 모든 소는 원래 받았던 선물과 같은 선물을 받거나, 원래 배정받은 것보다 선호하는 선물을 받아야 한다.
\(1\)부터 \(N\)까지의 각 \(i\)에 대해, 재배정 후 소 \(i\)가 받기를 기대할 수 있는 가장 선호하는 선물을 구하시오.
출제자: Benjamin Qi
배점
- 테스트 케이스 2-3은 \(N\le 8\)을 만족한다.
- 테스트 케이스 4-11에는 추가 제약이 없다.
출제자: Benjamin Qi
첫째 줄에 \(N\)이 주어진다. 다음 \(N\)개의 줄에 각 소의 선호 목록이 주어진다. 각 줄은 \(1\dots N\)의 순열임이 보장된다.
\(N\)개의 줄을 출력하며, \(i\)번째 줄에는 재배정 후 소 \(i\)가 받기를 기대할 수 있는 가장 선호하는 선물을 출력한다.
4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 41
3
2
4In this example, there are two possible reassignments:
- The original assignment: cow \(1\) receives gift \(1\), cow \(2\) receives gift \(2\), cow \(3\) receives gift \(3\), and cow \(4\) receives gift \(4\).
- Cow \(1\) receives gift \(1\), cow \(2\) receives gift \(3\), cow \(3\) receives gift \(2\), and cow \(4\) receives gift \(4\).
Observe that both cows \(1\) and \(4\) cannot hope to receive better gifts than they
were originally assigned. However, both cows \(2\) and \(3\) can.
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > February > Silver