Skip to content

13003: 【原3003】Strange Mushroom

题目

题目描述

author: zdq 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3003

Description

米莉是宇宙第一的厨师(自称), 最近在宇宙中寻找食材时发现了一种奇怪的蘑菇. 这种蘑菇每天都会固定分裂一次, 长度为x的蘑菇会分裂成两个长度分别为x-1和x+1的蘑菇, 但是长度为0的蘑菇是不存在的, 所以长度为1的蘑菇只能生长成长度为2的蘑菇. 现在米莉第一天有一个长度为2的蘑菇, 她想知道第n(1 <= n <= 10000)天她有多少个蘑菇.

比如: 第2天分裂成了2个蘑菇{M11, M31}(这里用Mi代表长度为i的蘑菇). 第3天长度为1的蘑菇成长为长度2, 长度为3的蘑菇分裂为两个, 于是有{M22, M41}. 第4天, 则为{M12, M33, M5*1}.

Input Format

一行, 一个整数n, 意义如上所述.

Output Format

一行, 一个整数, 代表米莉在第n天时拥有的蘑菇数量.

Sample Input

4

Sample Output

6

Hint

答案可能较大, 注意使用高精度保存及计算. 数据范围: 对于70%的测试点, n <= 30. 对于90%的测试点, n <= 100.

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!