← 返回题目
题库练习 坤坤的魔力鸡
← 上一题 下一题 →

A382 | 坤坤的魔力鸡

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

训练两年半的坤坤养了一只会魔法的鸡。这只鸡有以下特殊能力：
1. **魔法产蛋**：可以立即生出一个蛋并瞬间孵化成新鸡（每只鸡一生只能使用一次该能力）。
2. **体重限制**：新生鸡的体重 ≤ 原鸡体重的一半。
3. **魔力消失**：当鸡的体重为 1 时，无法再使用魔法。

给定初始鸡的体重 n，经过若干次魔法繁殖后，会生成一个体重序列。例如：
- 初始体重 4，可能的序列为 [4]、[4, 2]、[4, 2, 1]。

**问题**：对于给定的初始体重 n，计算所有可能的**不同序列**的数量。

输入格式

一行，一个正整数 表示初始的鸡的体重，n（1≤ n≤500）。

输出格式

一个整数，表示序列的数量

输入输出样例

输入 #1
6
输出 #1
6
C++ 编辑器
输入
输出