레이팅 미적용농부 존에게는 한 줄로 늘어선 \(N\)마리 (\(1 \leq N \leq 10^5\))의 소가 있다 (각각 \(1 \ldots N\)로 서로 다르게 식별된다). 농부 존은 소들이 증가하는 순서로 정렬되어 있는 것을 좋아하지만, 아쉽게도 지금은 순서가 뒤죽박죽이다. 과거에 농부 존은 소들을 정렬하기 위해 "버블 정렬" 같은 획기적인 알고리즘을 사용했지만, 오늘은 몹시 게으른 기분이다. 대신 그는 특정한 소 한 마리에게 한 번에 하나씩 "정리 좀 해"라고 소리칠 것이다. 소리를 들은 소는 (자신의 관점에서) 자신이 잘못된 위치에 있지 않도록 정리한다. 자신의 바로 오른쪽에 더 작은 ID의 소가 있는 동안, 둘은 자리를 바꾼다. 그다음, 자신의 바로 왼쪽에 더 큰 ID의 소가 있는 동안, 둘은 자리를 바꾼다. 이렇게 하면 소는 "정리"를 끝내며, 이 시점에는 그 소의 왼쪽 소는 더 작은 ID를, 오른쪽 소는 더 큰 ID를 가지게 된다.
농부 존은 소들의 부분집합을 하나 고른 다음, 이 부분집합을 (ID가 증가하는 순서로) 순회하며 각 소에게 차례로 소리치는 것을, \(N\)마리의 소가 모두 정렬될 때까지 반복하려 한다. 예를 들어, ID가 \(\{2, 4, 5\}\)인 소들의 부분집합을 골랐다면, 소 \(2\)에게 소리치고, 그다음 소 \(4\), 그다음 소 \(5\)에게 소리친다. \(N\)마리의 소가 아직 정렬되지 않았다면, 필요한 만큼 같은 소들에게 다시, 또다시 소리친다.
농부 존은 어떤 소들이 주의를 기울이고 있는지 확신할 수 없으므로, 이 부분집합의 크기를 최소화하고 싶어한다. 또한 농부 존은 숫자 \(K\)가 아주 행운의 숫자라고 생각한다. 반복해서 소리쳤을 때 결국 모든 소가 정렬되게 하는 최소 크기의 부분집합 중에서, 사전순으로 \(K\)번째로 작은 부분집합을 찾도록 도와주자.
\(\{1,\dots,N\}\)의 부분집합 \(S\)의 원소들을 증가하는 순서로 나열한 목록이 부분집합 \(T\)의 원소들을 증가하는 순서로 나열한 목록보다 사전순으로 작으면, \(S\)가 \(T\)보다 사전순으로 작다고 한다. 예를 들어 \(\{1, 3, 6\}\)은 \(\{1, 4, 5\}\)보다 사전순으로 작다.
점수 배분: 배점의 \(3/16\)에 해당하는 케이스에서는 \(N \leq 6\)이고 \(K = 1\)이다. 추가로 배점의 \(5/16\)에 해당하는 케이스에서는 \(K = 1\)이다. 추가로 배점의 \(8/16\)에 해당하는 케이스에서는 추가 제약이 없다.
출제자: Spencer Compton
출제자: Spencer Compton
첫째 줄에 정수 \(N\)이 주어진다. 둘째 줄에 정수 \(K\) (\(1 \leq K \leq 10^{18}\))가 주어진다. 셋째 줄에 왼쪽부터 오른쪽까지 소들의 번호를 나타내는 \(N\)개의 정수가 공백으로 구분되어 주어진다.
유효한 부분집합이 적어도 \(K\)개 존재함이 보장된다.
출력의 첫째 줄에 최소 부분집합의 크기를 출력한다. 나머지 줄에는 최소 크기의 부분집합 중 사전순으로 \(K\)번째로 작은 부분집합에 속한 소들의 ID를 한 줄에 하나씩, 증가하는 순서로 출력한다.
itout.in · 출력을 쓸 파일 itout.out4 1
4 2 1 32
1
4We start with the array \(\mathtt{\:4\:\; 2\:\; 1\:\; 3\:}\). After FJ yells at
the cow with ID 1, the array will be \(\mathtt{\:1\:\; 4\:\; 2\:\; 3\:}\). When FJ
yells at the cow with ID 4, the array will be
\(\mathtt{\:1\:\; 2\:\; 3\:\; 4\:}\). At which point, the array is sorted.
riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > December > Platinum