A382. 坤坤的魔力鸡
编程题
入门
知识点
题目描述
训练两年半的坤坤养了一只会魔法的鸡。这只鸡有以下特殊能力：
1. **魔法产蛋**：可以立即生出一个蛋并瞬间孵化成新鸡（每只鸡一生只能使用一次该能力）。
2. **体重限制**：新生鸡的体重 ≤ 原鸡体重的一半。
3. **魔力消失**：当鸡的体重为 1 时，无法再使用魔法。
给定初始鸡的体重
- 初始体重
**问题**：对于给定的初始体重
1. **魔法产蛋**：可以立即生出一个蛋并瞬间孵化成新鸡（每只鸡一生只能使用一次该能力）。
2. **体重限制**：新生鸡的体重 ≤ 原鸡体重的一半。
3. **魔力消失**：当鸡的体重为 1 时，无法再使用魔法。
给定初始鸡的体重
n，经过若干次魔法繁殖后，会生成一个体重序列。例如： - 初始体重
4，可能的序列为 [4]、[4, 2]、[4, 2, 1]。 **问题**：对于给定的初始体重
n，计算所有可能的**不同序列**的数量。输入格式
一行，一个正整数 表示初始的鸡的体重，n（1≤ n≤500）。
输出格式
一个整数，表示序列的数量
输入输出样例
输入 #1
6
输出 #1
6
说明/提示
对于
1.
2.
3.
4.
5.
6.
n = 6，所有可能的序列为： 1.
[6] 2.
[6, 1] 3.
[6, 2] 4.
[6, 2, 1] 5.
[6, 3] 6.
[6, 3, 1]