1850. How Many Trees?

单点时限: 2.0 sec

内存限制: 256 MB

A binary search tree is a binary tree with root k such that any node v reachable from its left has label (v)

Given a number n, can you tell how many different binary search trees may be constructed with a set of numbers of size n such that each element of the set will be associated to the label of exactly one node in a binary search tree?

输入格式

The input will contain a number 1 <= i <= 100 per line representing the number of elements of the set.

输出格式

You have to print a line in the output for each entry with the answer to the previous question.

样例

Input
1
2
3
Output
1
2
5

83 人解决,138 人已尝试。

130 份提交通过,共有 446 份提交。

4.3 EMB 奖励。

创建: 16 年,1 月前.

修改: 6 年,8 月前.

最后提交: 9 月,2 周前.

来源: UVa

题目标签