TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P6992
  • 题目
  • P6992考古
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 2s 256MB
    问题描述

    果市,一个拥有悠久历史的城市,2333年考古学家在果市发现了一个神秘的遗迹,这些勇敢而智慧的古队员准备进入这个遗迹,但要进入这个遗迹就需要通过一段天梯。而登上天梯必须要按照它要求的方法,否则就无法登上。它要求的方法为:

    1.可以直接登上比当前位置高$1$个单位高度的天梯。

    2.可以从当前阶梯往下退一级天梯(第一级天梯除外)。

    3.在连续退$k$步后,跳跃一次,跳跃的高度不超过$2^k$。比如说你现在位于第$i$级天梯,且之前从第$i+k$级天梯退下来,此时你可以跳到高度不超过(当前高度\(+ 2^k\))的任何一级天梯。每一次跳跃只算一次移动哦!

    开始的时候考古小队在第一级天梯。请你计算出最少的移动步数以登上最高一级天梯。

    为何考古搞得跟游戏历险一样?果市一定是一个魔性的城市!

    输入格式

    第1行:一个整数$N$,表示天梯级数。

    第2行:$N$个整数,依次为每层天梯梯的高度,保证递增。

    $1 \leq N \leq 200$,每级阶梯高度不超过$2^{31}-1$。

    输出格式

    一个整数,如果能登上天梯,输出最小步数,否则输出$-1$。

    样例输入

    5
    0 1 2 3 6

    样例输出

    7