2013年7月1日 星期一

2013/7/1 zj d916: 4. 高空煙火時間限制

// http://zerojudge.tw/ShowProblem?problemid=d916
#include<iostream>
#include<cstdio>
using namespace std;
int SJ[3100][1800];
int main()
{
    for(int i = 0; i <= 3009; i++)
    {
        SJ[i][0] = 1;
       
        for(int j = 1; j <= i; j++)
            SJ[i][j] = (SJ[i-1][j]%10000 + SJ[i-1][j-1]%10000)%10000;
       
    }
    int n, m;  scanf("%d %d", &n, &m);
    int sum = 1 + n;
    for(int i = 2; i+(i-1)*m <= n; i++)
    {
        int op = min((n-i-(i-1)*m),n-m*(i-1)-(n-i-(i-1)*m));
        sum += SJ[n-m*(i-1)][op];
        //sum += SJ[n-m*(i-1)][n-i-(i-1)*m];
        sum%=10000;  
    }
    printf("%d\n", sum); //system("pause");
}

沒有留言:

張貼留言