#PU1325. USACO 2023 US Open Contest, Bronze — Problem 3. Rotate and Shift
USACO 2023 US Open Contest, Bronze — Problem 3. Rotate and Shift
USACO 2023 US Open Contest, Bronze — Problem 3. Rotate and Shift
题目描述
Note: The time limit for this problem is 4s, 2x the default. To celebrate the start of spring, Farmer John's cows () have invented an intriguing new dance, where they stand in a circle and re-order themselves in a predictable way. Specifically, there are positions around the circle, numbered sequentially from to , with position following position . A cow resides at each position. The cows are also numbered sequentially from to . Initially, cow starts in position . You are told a set of positions that are "active", meaning the cows in these positions are the next to move (). In each minute of the dance, two things happen. First, the cows in the active positions rotate: the cow at position moves to position , the cow at position moves to position , and so on, with the cow at position moving to position . All of these moves happen simultaneously, so the after the rotation is complete, all of the active positions still contain exactly one cow. Next, the active positions themselves shift: becomes , becomes , and so on (if for some active position, then circles back around to ). Please calculate the order of the cows after minutes of the dance ().
输入格式
The first line contains three integers , , and . The second line contains integers representing the initial set of active positions . Recall that and that these are given in increasing order.
输出格式
(见题面原文)
数据范围
Inputs 2-7: Inputs 8-13: No additional constraints. Problem credits: Claire Zhang
样例
样例 1
5 3 4
0 2 3
1 2 3 4 0
For 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]