4946：[POI 2010] ZAB-Frog

# [POI 2010] ZAB-青蛙 ## 题目描述 在一条笔直且很长的 Byteotian 小溪河床上，有 $n$ 块露出水面的石头，它们到小溪源头的距离依次为 $p_1 \lt p_2 \lt \cdots < p_n$。 一只小青蛙正坐在其中一块石头上，准备开始跳跃训练。 每次跳跃时，青蛙都会跳到**距离它当前所在石头第 $k$ 近**的那块石头上。 具体规则： 如果青蛙在石头 $p_i$ 上，它会跳到满足以下条件的石头 $p_j$ 上： 1. 到 $p_i$ 的距离**严格小于** $p_j$ 到 $p_i$ 距离的石头数量 **不超过** $k$； 2. 到 $p_i$ 的距离**小于等于** $p_j$ 到 $p_i$ 距离的石头数量 **大于** $k$。 如果满足条件的石头 $p_j$ 不唯一，青蛙会选择**最靠近源头**（编号最小）的那块。 请你计算：青蛙从**每一块石头**出发，跳跃 $m$ 次后，最终会停在哪块石头上？ ## 输入格式 第一行：三个整数 $n, k, m$ - $n$：石头数量 - $k$：跳跃规则参数 - $m$：跳跃次数（$1 \le m \le 10^{18}$） 第二行：$n$ 个严格递增的整数 $p_1,p_2,\dots,p_n$，表示石头的位置 ## 输出格式 一行 $n$ 个整数 $r_1,r_2,\dots,r_n$ $r_i$ 表示从第 $i$ 块石头出发，跳 $m$ 次后停留的石头编号 ## 输入样例1： ``` 5 2 4 1 2 4 7 10 ``` ## 输出样例1： ``` 1 1 3 1 1 ``` ## 提示 ### 样例 #1 解释 图中展示了青蛙从每块石头出发，**单次跳跃**会跳到的位置。  标签：P3509|动态规划 DP|2010|倍增|单调队列|POI（波兰）|深度优先搜索 DFS ## 来源 P3509|[POI 2010] ZAB-Frog