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?






    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