8191: USACO 2023 US Open Contest, Bronze Problem 3. Rotate and Shift
[Creator : ]
Description
To celebrate the start of spring, Farmer John's N cows $(1≤N≤2⋅10^5)$ have invented an intriguing new dance, where they stand in a circle and re-order themselves in a predictable way.
Specifically, there are N positions around the circle, numbered sequentially from 0 to N−1, with position 0 following position N−1. A cow resides at each position. The cows are also numbered sequentially from 0 to N−1. Initially, cow i starts in position i. You are told a set of K positions $0=A_1<A_2<…<A_K<N$ that are "active", meaning the cows in these positions are the next to move (1≤K≤N).
In each minute of the dance, two things happen. First, the cows in the active positions rotate: the cow at position $A_1$ moves to position $A_2$, the cow at position $A_2$ moves to position $A_3$, and so on, with the cow at position $A_K$ moving to position $A_1$. All of these K 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: $A_1$ becomes $A_1+1$, $A_2$ becomes $A_2+1$, and so on (if $A_i=N−1$ for some active position, then $A_i$ circles back around to 0).
Please calculate the order of the cows after T minutes of the dance $(1≤T≤10^9)$.
Specifically, there are N positions around the circle, numbered sequentially from 0 to N−1, with position 0 following position N−1. A cow resides at each position. The cows are also numbered sequentially from 0 to N−1. Initially, cow i starts in position i. You are told a set of K positions $0=A_1<A_2<…<A_K<N$ that are "active", meaning the cows in these positions are the next to move (1≤K≤N).
In each minute of the dance, two things happen. First, the cows in the active positions rotate: the cow at position $A_1$ moves to position $A_2$, the cow at position $A_2$ moves to position $A_3$, and so on, with the cow at position $A_K$ moving to position $A_1$. All of these K 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: $A_1$ becomes $A_1+1$, $A_2$ becomes $A_2+1$, and so on (if $A_i=N−1$ for some active position, then $A_i$ circles back around to 0).
Please calculate the order of the cows after T minutes of the dance $(1≤T≤10^9)$.
Input
The first line contains three integers N, K, and T.
The second line contains K integers representing the initial set of active positions $A_1,A_2,…A_K$. Recall that $A_1=0$ and that these are given in increasing order.
The second line contains K integers representing the initial set of active positions $A_1,A_2,…A_K$. Recall that $A_1=0$ and that these are given in increasing order.
Output
Output the order of the cows after T minutes, starting with the cow in position 0, separated by spaces.
Sample 1 Input
5 3 4
0 2 3
Sample 1 Output
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]