Description
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 32-bit integer. K is a non-negative integer fit in signed 32-bit 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 N-th year in a line for each case.
Sample Input
10000 0 101 1 10 2 1221 128 0 0
Sample Output
9999 5050 221 2147483647
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 100005
#define MAXN 16005
#define mod 1000000000
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;
ll n,m,k,ans,cnt,tot,flag;
ll dp[maxn],sum[maxn];
ll xx=1234567890;
ll solve()
{
ll i,j,d,t;
dp[0]=sum[0]=0;
for(i=1;i<=n;i++)
{
dp[i]=i+sum[i-1]-sum[max(0LL,i-k-1)];
sum[i]=sum[i-1]+dp[i];
if(dp[i]>xx) return dp[i];
}
return dp[n];
}
int main()
{
ll i,j,t;
while(scanf("%lld%lld",&n,&k),n|k)
{
n--;
if(k==0)
{
printf("%lld\n",min(n,xx+1));
continue ;
}
ans=solve();
printf("%lld\n",ans);
}
return 0;
}
/*
10000 0
101 1
10 2
1221 128
0 0
*/