서로 다른 \mathbf{N}개의 항목 x_1, x_2, \dots, x_\mathbf{N}을 정렬하고 싶다.
하지만 불행히도 두 항목을 직접 비교할 방법이 없다.
당신에게 가능한 것은,
세 항목을 주면 그 셋 중에서 중앙값(median),
즉 최솟값도 최댓값도 아닌 항목이 무엇인지 알아내는 것뿐이다.
예를 들어 \mathbf{N} = 5이고 다음을 알고 있다고 하자:
- x_1은 \{x_1, x_2, x_3\}의 중앙값이다.
- x_2은 \{x_2, x_3, x_4\}의 중앙값이다.
- x_3은 \{x_3, x_4, x_5\}의 중앙값이다.
그러면 정렬된 순서는
x_4, x_2, x_1, x_3, x_5 또는 그 역순인 x_5, x_3, x_1, x_2, x_4임이 보장된다.
중앙값 정보만으로는 어떤 순서와 그 역순을 구분하는 것이 불가능하다는 점에 유의하라.
어떤 세 원소에 대해서도 중앙값 질의의 결과는
순서를 뒤집어도 동일하기 때문이다.
당신의 프로그램은 \mathbf{T}개의 리스트(각각 \mathbf{N}개 원소)를 정렬해야 하며,
전체를 통틀어 중앙값 질의를 최대 \mathbf{Q}번만 사용할 수 있다
(즉, 리스트 하나당 평균적으로 \mathbf{Q} / \mathbf{T}번 질의).
각 테스트 케이스에서 올바른 순서 또는 그 역순을 찾아내면 정답으로 인정된다.
각 케이스의 실제 순서는 가능한 모든 순서 중에서 균등 무작위로 생성되며,
다른 어떤 정보와도 독립적이다.
ログインしないとコードを書けません。