BRTREE  Bread Tree
English  Vietnamese 
Breadtree is a kind of tree that produces bread. At its first year, a breadtree is only a node with a bread of weight 0 on this node which is also called zeronode. Every year after that, the weight of bread on each node of the tree will increase by 1, and another branch with a zeronode will grow at the end of each node. However, there is a limit of branches on each node. That is, when the number of branches of a node reaches the limit, there won't be any more branches, but the weight of its bread will still increase. What's more, a breadtree remains unchanged when the total weight of bread is larger than 1234567890.
Input
There are two integers N and K on each line. N is a positive integer fit in signed 32bit integer. K is a nonnegative integer fit in signed 32bit integer. An N equals to 0 signals the end of input, which should not be processed.
Output
Output the total weight of bread on a breadtree with branches limit K in the Nth year in a line for each case.
Example
Input: 10000 0 101 1 10 2 1221 128 0 0 Output: 9999 5050 221 2147483647
hide comments
noedelorme:
20210720 02:11:51
[Fixed]


noedelorme:
20210719 22:52:36
@legsleg True, my bad :) 

legsleg:
20210719 10:07:48
The worstcase input regarding runningtime is actually (most probably) something else. Last edit: 20210719 10:11:07 

jacomo:
20210717 13:10:25
@noedelorme: It's done in under 0.1s Last edit: 20210717 13:10:42 

noedelorme:
20210717 08:39:22
You can try with the worst case, which is the following (because 2147483647 is the maximal positive signed 32bit integer) :


jacomo:
20210713 09:16:24
Getting always a TLE , but don't know why.

Added by:  Race with time 
Date:  20090124 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  ZOJ Monthly, January 2009  A 