CF9D.How many trees?
普及+/提高
通过率:0%
时间限制:1.00s
内存限制:64MB
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 n 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 1 to n. 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 h. 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?
在一份非常古老的文本文件中,记载着“大智慧”。这份智慧是如此之伟大,以至于无人能够破译它,甚至连主帧(Mainframe)最年长的居民——冯(Phong)也不能。但他仍从中获取了一些信息。例如,他得知:用户(User)启动游戏只是为了取乐——随后可怕的“游戏方块”(Game Cubes)便会从天而降,砸向城市,给那些无法赢得游戏的模块(modules)带来死亡……
当然,自从守卫鲍勃(Bob)出现在主帧后,许多模块便不再惧怕游戏方块了。因为鲍勃(迄今依然存活)从未被用户击败过;而且他总会主动干预游戏方块——这是他的程序设定。
然而,当游戏方块坠落在“迷失角”(Lost Angles)时,就可能发生不愉快的情况。因为那里住着一个讨厌的病毒——十六进制(Hexadecimal),她……嗯……非常古怪。而且她极其热衷于玩游戏。因此,鲍勃不得不先与她对战,然后再面对用户。
这一次,十六进制设计了如下娱乐项目:鲍勃必须跃过所有含 $ n $ 个节点的二叉搜索树(binary search trees)。我们提醒你:二叉搜索树是一种二叉树,其中每个节点具有互异的关键字(key);对任意节点而言,其左子树中所有节点的关键字均严格小于该节点的关键字,其右子树中所有节点的关键字均严格大于该节点的关键字。所有关键字均为 $ 1 $ 到 $ n $ 之间的互异正整数。此类树的每个节点最多有两个子节点,也可能没有子节点(即为叶子节点)。
在十六进制的游戏中,所有树彼此不同,但每棵树的高度均不小于 $ h $。本题中,“高度”定义为从根节点到最远叶子节点的路径上所经过的节点总数(包含根节点和该叶子节点本身)。每当鲍勃跃过一棵树,该树即消失。当所有树均消失后,鲍勃便可获得进入游戏方块的权限。他知道,在最坏情况下,自己需要跃过的树的数量。那么,你知道吗?
输入格式
The input data contains two space-separated positive integer numbers n and h (n ≤ 35, h ≤ n).
输入数据包含两个以空格分隔的正整数 n 和 h(n≤35,h≤n)。
输出格式
Output one number — the answer to the problem. It is guaranteed that it does not exceed 9·1018.
输出一个数字——该问题的答案。保证该答案不超过 9⋅1018。
输入输出样例
输入#1
3 2
输出#1
5
输入#2
3 3
输出#2
4
输入解题思路,AI测评打分。不知道怎么写?