问题 2428. -- 宁静与九连环

2428: 宁静与九连环

时间限制: 0 Sec  内存限制: 128 MB
提交: 0  解决: 0
[上一题][提交][讨论版][状态][下一题]

题目描述

        数学成绩出来,某T折戟沉沙,涉险及格。而宁静折取桂冠。然而为了E文测验,宁静带了个九连环回学校供她欣赏。
        宁静:这个就是经典的九连环啦!九连环的每个环互相制约,只有第一环能够自由上下。要想下/上第n个环,就必须满足两个条件:
        一、第n-1个环在架上;
        二、第n-1个环前面的环全部不在架上。
        这样一来的话如果我想解第一个环的话就是这样,两个环的话我先也可以直接下。三个环的时候就这样这样:
        1、下1环
        2、下3环
        3、上1环
        4、下2环
        5、下1环
        某T:那么,下9个环呢?
        宁静双手赛百鸟,卡擦卡擦在10分钟之内全部下了。
        某T:好玩好玩~,这个给我。
        宁静:喂喂……
        某T:这样吧,明天我问你当我要下N个环时需要多少步,如果你说出来的话一切好说,说不出来这个玩意归我了。
        宁静:……(悲哀)
        宁静无论如何也不会将时间浪费于和某T折腾,于是他想到了oier……

输入 [njyjlh.in]

一个正整数N(1< =N< =800),代表要拆卸的环数

输出 [njyjlh.out]

一个正整数M,代表所需的步数

样例输入

20

样例输出

699050

提示

标签

[上一题][提交][讨论版][状态][下一题]