← 返回题目列表

Codeforces · 9/D

D. 有多少棵树?

中文机器翻译题面 查看原题

在一份非常古老的文本文件中写着“大智慧”。这种智慧是如此伟大,以至于没有人能够破译它,甚至包括大型机居民中最年长的冯。但他还是设法从那里得到了一些信息。例如,他设法了解到用户为了娱乐而推出游戏 - 然后可怕的游戏立方体掉落在城市上,给那些无法赢得游戏的模块带来死亡......

当然,当后卫鲍勃出现在大型机中时,许多模块不再害怕游戏立方体。因为鲍勃(他还活着)从未被用户击败过,而且他总是干预游戏立方体,因为他被编程为这样。

然而,当游戏立方体在失落角度掉落时,可能会发生不愉快的情况。因为那里生活着一种令人讨厌的病毒——十六进制,它……嗯……非常奇怪。而且她非常喜欢玩。因此,无论愿意与否,鲍勃都必须先与她一起玩,然后再与用户一起玩。

这次 Hexadecimal 发明了以下娱乐:Bob 必须跳过有 n 个节点的二叉搜索树。我们应该提醒您,二叉搜索树是一棵二叉树,每个节点都有一个不同的键,对于每个节点,以下情况成立:节点的左子树仅包含键小于该节点键的节点,节点的右子树仅包含键大于该节点键的节点。所有的键都是从1到n的不同正整数。这种树的每个节点最多可以有两个子节点,或者根本没有子节点(在节点是叶子的情况下)。

在Hexadecimal的游戏中,所有的树都是不同的,但是每棵树的高度都不低于h。在这个问题中,“高度”代表从根到最远叶子的最大节点数,包括根节点和叶子本身。当鲍勃跳过一棵树时,它就消失了。当没有剩下的树时,鲍勃可以访问立方体。他知道在最坏的情况下他必须跳过多少棵树。你呢?

输入

输入数据包含两个空格分隔的正整数 n 和 h (n ≤ 35, h ≤ n)。

输出

输出一个数字——问题的答案。保证不超过9·1018。

示例

输入 #1

3 2

输出 #1

5

输入 #2

3 3

输出 #2

4