Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2577
How Many Leaves Left?

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Leftleaf loves left leaf very much. When she creats a binary tree with N nodes, she always makes the left leaves as many as possible, guaranteed the tree does not have any right leaf. Of course she is excellent enough to do so.

Rightleaf does not think in the same way. When she found the left-leaf tree, she was very angry and took out the leaves, of course not the right leaves but the left ones. Luckily, Leftleaf went back in time, and Rightleaf just had T minutes to destroy the tree.

Now, it's turn for you to calculate how many leaves left at most, since Leftleaf might make her tree in several ways and Rightleaf took out the leaves without thinking carefully. We also knew that Rightleaf took out M leaves per minute.

Note that, the root of the tree is not considered as left or right leaf .


The input consists of a serie of three nonnegative integers N, T and M(N, T, M < 32768), separated by a space. Three numbers per line. N=M=T=0 signals the end of the file.


For each cases, just output one number: the number of leaves left at most. One number per line.

Sample Input
1 1 1
3 1 1
3 1 2
4 1 1
4 1 2
0 0 0
Sample Output

Author: DENG, Wenliang
Source: ZOJ Monthly, October 2005
Submit    Status