CF9D.How many trees?

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

In one very old text file there was written Great Wisdom. This Wisdom was so Great that nobody could decipher it, even Phong — the oldest among the inhabitants of Mainframe. But still he managed to get some information from there. For example, he managed to learn that User launches games for pleasure — and then terrible Game Cubes fall down on the city, bringing death to those modules, who cannot win the game...

For sure, as guard Bob appeared in Mainframe many modules stopped fearing Game Cubes. Because Bob (as he is alive yet) has never been defeated by User, and he always meddles with Game Cubes, because he is programmed to this.

However, unpleasant situations can happen, when a Game Cube falls down on Lost Angles. Because there lives a nasty virus — Hexadecimal, who is... mmm... very strange. And she likes to play very much. So, willy-nilly, Bob has to play with her first, and then with User.

This time Hexadecimal invented the following entertainment: Bob has to leap over binary search trees with nn nodes. We should remind you that a binary search tree is a binary tree, each node has a distinct key, for each node the following is true: the left sub-tree of a node contains only nodes with keys less than the node's key, the right sub-tree of a node contains only nodes with keys greater than the node's key. All the keys are different positive integer numbers from 11 to nn . Each node of such a tree can have up to two children, or have no children at all (in the case when a node is a leaf).

In Hexadecimal's game all the trees are different, but the height of each is not lower than hh . In this problem «height» stands for the maximum amount of nodes on the way from the root to the remotest leaf, the root node and the leaf itself included. When Bob leaps over a tree, it disappears. Bob gets the access to a Cube, when there are no trees left. He knows how many trees he will have to leap over in the worst case. And you?

树量有多少?(没打错,就是树的“量”)

在一个非常古老的文本文件中写着伟大的智慧。这个智慧是如此伟大,以至于连主机城的居民中最古老的 Phong 也无法解读。但他仍然设法从中获取了一些信息。例如,他设法了解到用户启动游戏是为了快乐 —— 然后可怕的游戏方块会落在城市上,给那些无法赢得游戏的模块带来死亡...

毫无疑问,当警卫 Bob 出现在主机城时,许多模块停止害怕游戏方块。因为 Bob(尽管他还活着)从未被用户击败过,而且他总是干涉游戏方块,因为他被编程成这样。

然而,不愉快的情况可能会发生,当一个游戏方块落在迷失之角时。因为那里住着一个讨厌的病毒 —— Hexadecimal,她是... 嗯... 非常奇怪的。而且她非常喜欢玩。所以,不管愿意与否,Bob 必须先和她玩,然后再和用户玩。

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

在 Hexadecimal 的游戏中,所有的树都是不同的,但每个树的高度不低于 hh。在这个问题中,“高度”代表从根到最远的叶子节点之间的节点数的最大值,包括根节点和叶子节点本身。当 Bob 跳过一棵树时,它会消失。当没有树剩下时,Bob 就可以访问一个方块。他知道在最坏的情况下他将不得不跳过多少棵树。那么你呢?

感谢Macw提供翻译

输入格式

The input data contains two space-separated positive integer numbers nn and hh ( n<=35n<=35 , h<=nh<=n ).

输入包含两个整数nnhh。其中n35,hnn \le 35, h \le n

输出格式

Output one number — the answer to the problem. It is guaranteed that it does not exceed 910189·10^{18} .

输出一个整数,代表本道题的答案。题目保证答案不超过9×10189 \times 10^{18}

输入输出样例

  • 输入#1

    3 2
    

    输出#1

    5
  • 输入#2

    3 3
    

    输出#2

    4

说明/提示

请注意,本题空间限制为64MB,是默认空间限制的二分之一。

首页