#1732. 跳跃机器人(广搜)
跳跃机器人(广搜)
题目描述
地上有一排格子,共 个位置。机器猫站在第一个格子上,需要取第 个格子里的东西。
机器猫当然不愿意自己跑过去,所以机器猫从口袋里掏出了一个机器人!这个机器人的行动遵循下面的规则:
- 初始时,机器人位于 号格子
- 若机器人目前在 格子,那么它可以跳跃到 里的一个格子(不允许跳出界)
问机器人最少需要多少次跳跃,才能到达 号格子。
输入格式
仅一行,一个正整数,表示 。
输出格式
仅一行,一个正整数,表示最少跳跃次数。
样例 #1
样例输入 #1
30
样例输出 #1
6
样例 #2
样例输入 #2
50
样例输出 #2
7
样例 #3
样例输入 #3
64
样例输出 #3
6
样例 #4
样例输入 #4
63
样例输出 #4
8
提示
样例解释
第一组样例:
第二组样例:
第三组样例:
第四组样例:
请注意在本组样例中, 不能通过 得到,因为格子总数为 ,没有第 个格子。
数据规模与约定
对于 的数据,有 。