#PU1325. USACO 2023 US Open Contest, Bronze — Problem 3. Rotate and Shift

    ID: 1638 传统题 4000ms 256MiB 尝试: 0 已通过: 0 难度: 普及 上传者: 标签>USACO赛事:open23来源:usaco.orgscoring:equal_test_cases分块

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 NN cows (1≤N≤2⋅1051 \leq N \leq 2 \cdot 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 NN positions around the circle, numbered sequentially from 00 to N−1N-1, with position 00 following position N−1N-1. A cow resides at each position. The cows are also numbered sequentially from 00 to N−1N-1. Initially, cow ii starts in position ii. You are told a set of KK positions 0=A1<A2<…<AK<N0=A_1<A_2< \ldots< A_K<N that are "active", meaning the cows in these positions are the next to move (1≤K≤N1 \leq K \leq N). In each minute of the dance, two things happen. First, the cows in the active positions rotate: the cow at position A1A_1 moves to position A2A_2, the cow at position A2A_2 moves to position A3A_3, and so on, with the cow at position AKA_K moving to position A1A_1. All of these KK 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: A1A_1 becomes A1+1A_1+1, A2A_2 becomes A2+1A_2+1, and so on (if Ai=N−1A_i = N-1 for some active position, then AiA_i circles back around to 00). Please calculate the order of the cows after TT minutes of the dance (1≤T≤1091\le T\le 10^9).

输入格式

The first line contains three integers NN, KK, and TT. The second line contains KK integers representing the initial set of active positions A1,A2,…AKA_1,A_2, \ldots A_K. Recall that A1=0A_1 = 0 and that these are given in increasing order.

输出格式

(见题面原文)

数据范围

Inputs 2-7: N≤1000,T≤10000N \leq 1000, T \leq 10000 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]