Responsive image

问题 C: 鼠鼠的数

问题 C: 鼠鼠的数

时间限制: 1 Sec  内存限制: 125 MB
提交: 0  解决: 27
[提交][状态][讨论版][命题人:]

题目描述

鼠鼠给出自然数n，它想要按如下方式构造数列：
1.只有一个数字n的数列是一个合法的数列。
2.在一个合法的数列的末尾加入一个自然数，但是这个自然数不能超过该数列最后一项的一半，可以得到一个新的合法数列。
请你帮鼠鼠求出，一共有多少个合法的数列，两个合法数列a，b不同当且仅当两数列长度不同或存在一个正整数i≤|a|,使得ai≠bi。

输入描述

输入只有一行一个数，表示n。

输出描述

输出一行一个整数，表示合法的数列个数。

样例输入

6

样例输出

6

提示


样例1解释

满足条件的数列为：

6

6   1

6   2

6   3

6   2   1

6   3   1

对于全部的测试点，保证1≤n≤1000。

[提交][状态]
ACM算法攻关部