Welcome to ZOJ
Select Problem
ZOJ Problem Set - 1470
How Many Trees?

Time Limit: 2 Seconds      Memory Limit: 65536 KB

The balanced binary tree is defined recursively as follows:

1. The difference in the depth of its left child tree and right child tree is at most 1.

2. Its left child tree is a balanced binary tree.

3. Its right child tree is also a balanced binary tree.

Now it is your job to calculate the number of balanced binary trees with given number of nodes and leaves.


The input consists of multiple tests. Each test consists of 2 numbers n and m in a single line, the number of the nodes and the number of leaves. (0 < m <= n <= 20)


The number of balanced binary trees which have exactly n nodes and m leaves.

Sample Input

5 2
15 9

Sample Output


Author: TANG, Jiqing
Source: ZOJ Monthly, December 2002
Submit    Status