시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 1456 | 569 | 457 | 39.060% |
HCPC 2021에 참석한 $N \times N$명의 사람들이 의자가 정사각형 형태로 배치된 대회장에서 대회를 한다. 모든 의자에는 서로 다른 추첨번호가 적혀있으며 HCPC 2021의 마지막에는 아래에 설명된 규칙에 따라 특별상을 받을 사람 한 명을 정한다.
HCPC 2021에 참가한 지원이는 자신의 실력이 부족해서 수상권이 아니라고 생각하였고, 실력과 무관하게 받을 수 있는 특별상을 노리고 있다.
아래 예시를 참고하자.
위와 같은 의자 배열이 있다고 가정하자. 이를 네 개의 구역으로 나누면 아래와 같다.
나누어진 구역의 왼쪽 위 구역을 다시 네 개의 구역으로 나누면 아래와 같다.
여기에서 추첨번호가 두 번째로 낮은 사람을 고르면 아래와 같다.
이와 같은 작업을 모든 영역에 대해 실행하면 아래와 같다.
따라서 특별상을 받는 추첨번호는 아래와 같다.
따라서, 추첨번호 $3$이 적힌 의자에 앉은 참가자가 특별상을 받는다.
의자 각각에 적혀 있는 추첨번호가 주어질 때, 지원이가 HCPC 2021에서 경품을 받을 수 있으려면 어떤 의자에 앉아야 하는지 계산하는 프로그램을 작성하시오.
첫 번째 줄에는 정수 $N$이 주어진다. (단, $N = 2^m$, $0 \le m \le 10$, $m$은 정수)
두 번째 줄부터 $N$개 줄의 $i$번째 줄에는 $i$번째 줄에 있는 의자에 적힌 추첨번호가 주어진다. 각 줄에는 $N$개의 추첨번호가 공백으로 구분되어 주어진다.
추첨번호는 $2^{31}$ 보다 작은 음이 아닌 정수이고, 모든 추첨번호는 서로 다름이 보장된다.
지원이가 HCPC 2021에서 경품을 받기 위해 앉아야 하는 의자에 적힌 추첨번호를 출력한다.
2 2 0 3 1
1
4 15 7 13 5 4 2 1 9 0 10 8 12 3 11 14 6
4
University > 한양대학교 > 제8회 한양대학교 프로그래밍 경시대회 > Advanced Division I번