[POI2010] ZAB-Frog
题意翻译
有 $n$ 个点,升序给出每个点到起点的距离。有编号为 $1 \sim n$ 的 $n$ 只青蛙分别在第 $1 \sim n$ 个点上,每次它们会跳到距离自己第 $k$ 远的点上。
如果有相同距离的点,就跳到下标更小的点上。
求跳 $m$ 次之后,第 $i$ 只的青蛙在哪个点上。
输入共一行三个整数:代表 $n, k, m$。
输出共一行 $n$ 个整数,代表每只青蛙最终所处在的点。
题目描述
On the bed of one particularly long and straight Byteotian brook there lie ![](http://main.edu.pl/images/OI17/zab-en-tex.1.png) rocks jutting above the water level.
Their distances from the brook's spring are ![](http://main.edu.pl/images/OI17/zab-en-tex.2.png) respectively.
A small frog sitting on one of these is about to begin its leaping training.
Each time the frog leaps to the rock that is the ![](http://main.edu.pl/images/OI17/zab-en-tex.3.png)-th closest to the one it is sitting on.
Specifically, if the frog is sitting on the rock at position ![](http://main.edu.pl/images/OI17/zab-en-tex.4.png), then it will leap onto such ![](http://main.edu.pl/images/OI17/zab-en-tex.5.png) that:
![](http://main.edu.pl/images/OI17/zab-en-tex.6.png) and ![](http://main.edu.pl/images/OI17/zab-en-tex.7.png) If ![](http://main.edu.pl/images/OI17/zab-en-tex.8.png) is not unique, then the frog chooses among them the rock that is closest to the spring.
On which rock the frog will be sitting after ![](http://main.edu.pl/images/OI17/zab-en-tex.9.png) leaps depending on the rock is started from?
输入输出格式
输入格式
The first line of the standard input holds three integers, ![](http://main.edu.pl/images/OI17/zab-en-tex.10.png), ![](http://main.edu.pl/images/OI17/zab-en-tex.11.png) and ![](http://main.edu.pl/images/OI17/zab-en-tex.12.png) (![](http://main.edu.pl/images/OI17/zab-en-tex.13.png), ![](http://main.edu.pl/images/OI17/zab-en-tex.14.png)), separated by single spaces, that denote respectively: the number of rocks, the parameter ![](http://main.edu.pl/images/OI17/zab-en-tex.15.png), and the number of intended leaps.
The second line holds ![](http://main.edu.pl/images/OI17/zab-en-tex.16.png) integers ![](http://main.edu.pl/images/OI17/zab-en-tex.17.png) (![](http://main.edu.pl/images/OI17/zab-en-tex.18.png)), separated by single spaces, that denote the positions of successive rocks on the bed of the brook.
输出格式
Your program should print a single line on the standard output, with ![](http://main.edu.pl/images/OI17/zab-en-tex.19.png) integers ![](http://main.edu.pl/images/OI17/zab-en-tex.20.png) from the interval ![](http://main.edu.pl/images/OI17/zab-en-tex.21.png) in it, separated by single spaces.
The number ![](http://main.edu.pl/images/OI17/zab-en-tex.22.png) denotes the number of the rock that the frog ends on after making ![](http://main.edu.pl/images/OI17/zab-en-tex.23.png) leaps starting from the rock no. ![](http://main.edu.pl/images/OI17/zab-en-tex.24.png) (in the input order).
输入输出样例
输入样例 #1
5 2 4
1 2 4 7 10
输出样例 #1
1 1 3 1 1
说明
$1 \le k \lt n \le 10^6$,$1 \le m \le 10^{18}$,$1 \le p_1 \lt p_2 \lt ... \lt p_n \le 10^{18}$