• 应用
• 登录
• 注册

# P3509 [POI2010]ZAB-Frog

• 33通过
• 114提交
• 题目提供者洛谷OnlineJudge
• 标签 倍增 动态规划,动规,dp 深度优先搜索,DFS POI 2010 高性能
• 难度 提高+/省选-
• 时空限制 1s / 128MB
• 提示：收藏到任务计划后，可在首页查看。

## 题目描述

On the bed of one particularly long and straight Byteotian brook there lie rocks jutting above the water level.

Their distances from the brook's spring are 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 -th closest to the one it is sitting on.

Specifically, if the frog is sitting on the rock at position , then it will leap onto such that:

and If 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 leaps depending on the rock is started from?

数轴上有n个点，有一个青蛙在这些点上跳；

规则是每次向距当前点第k小的点跳，如果有相同距离则向下标较小的跳；

求从每个点出发跳了m次后在哪里；

## 输入输出格式

输入格式：

The first line of the standard input holds three integers, , and (, ), separated by single spaces, that denote respectively: the number of rocks, the parameter , and the number of intended leaps.

The second line holds integers (), 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 integers from the interval in it, separated by single spaces.

The number denotes the number of the rock that the frog ends on after making leaps starting from the rock no. (in the input order).

## 输入输出样例

输入样例#1： 复制
5 2 4
1 2 4 7 10
输出样例#1： 复制
1 1 3 1 1
提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。