레이팅 미적용*참고: 이 문제의 시간 제한은 기본의 2배인 4초이다.*
봄의 시작을 기념하기 위해, 농부 존의 \(N\)마리 소들(\(1 \leq N \leq 2 \cdot 10^5\))은 원을 이루어 서서 예측 가능한 방식으로 자리를 바꾸는 흥미로운 새 춤을 고안했다.
구체적으로, 원 둘레에 \(N\)개의 위치가 있으며, \(0\)부터 \(N-1\)까지 차례대로 번호가 매겨져 있고, 위치 \(N-1\) 다음에 위치 \(0\)이 온다. 각 위치에는 소 한 마리가 있다. 소들에게도 \(0\)부터 \(N-1\)까지 차례대로 번호가 매겨져 있다. 처음에 소 \(i\)는 위치 \(i\)에서 시작한다. "활성" 위치 \(K\)개의 집합 \(0=A_1
춤의 매 분마다 두 가지 일이 일어난다. 먼저, 활성 위치에 있는 소들이 회전한다: 위치 \(A_1\)의 소가 위치 \(A_2\)로, 위치 \(A_2\)의 소가 위치 \(A_3\)로 이동하며, 이런 식으로 위치 \(A_K\)의 소가 위치 \(A_1\)로 이동한다. 이 \(K\)번의 이동은 모두 동시에 일어나므로, 회전이 끝난 후에도 모든 활성 위치에는 정확히 한 마리의 소가 있다. 다음으로, 활성 위치 자체가 이동한다: \(A_1\)은 \(A_1+1\)이 되고, \(A_2\)는 \(A_2+1\)이 되는 식이다 (어떤 활성 위치에 대해 \(A_i = N-1\)이면, \(A_i\)는 \(0\)으로 되돌아간다).
춤을 \(T\)분 춘 후의 소들의 순서를 계산하라 (\(1\le T\le 10^9\)).
출제자: Claire Zhang
배점
- 입력 2-7: \(N \leq 1000, T \leq 10000\)
- 입력 8-13: 추가 제약 조건이 없다.
출제자: Claire Zhang
첫째 줄에 세 정수 \(N\), \(K\), \(T\)가 주어진다.
둘째 줄에 초기 활성 위치 집합을 나타내는 \(K\)개의 정수 \(A_1,A_2, \ldots A_K\)가 주어진다. \(A_1 = 0\)이고 증가하는 순서로 주어짐을 기억하라.
\(T\)분 후의 소들의 순서를 위치 \(0\)의 소부터 시작하여 공백으로 구분해 출력한다.
5 3 4
0 2 31 2 3 4 0For the example above, here are the cow orders and \(A\) for the first four
timesteps:
Initial, T = 0: order = [0 1 2 3 4], A = [0 2 3]
T = 1: order = [3 1 0 2 4]
T = 1: A = [1 3 4]
T = 2: order = [3 4 0 1 2]
T = 2: A = [2 4 0]
T = 3: order = [2 4 3 1 0]
T = 3: A = [3 0 1]
T = 4: order = [1 2 3 4 0]
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > US Open > Bronze