Crisis of HDU

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8153 Accepted Submission(s): 2522

Problem Description

話說(shuō)上回講到HDU大戰(zhàn)東洋小茍，結(jié)果自然是中方大勝，這一戰(zhàn)也使得海東集團(tuán)在全球同行業(yè)中的地位更加鞏固。隨著集團(tuán)的發(fā)展，很多創(chuàng)業(yè)時(shí)期的元老逐步功成身退，先是8600移民海外，然后是linle夫婦退隱山林，逐漸的，最初眾多的元老只剩下XHD夫婦和Wiskey三人了。
到了2020年，因?yàn)閿U(kuò)張過(guò)度加上老鼠數(shù)量逐年減少，公司的發(fā)展遇到了前所未有的危機(jī)，此時(shí)集團(tuán)已經(jīng)沒(méi)有任何流動(dòng)資金，更可怕的是，這個(gè)時(shí)候，wiskey也決定退出了！
退出本身并不麻煩，麻煩的是，退出的人需要取走相應(yīng)比例（1/3）金額的資產(chǎn)。
假設(shè)公司此時(shí)一共有n種價(jià)值的資產(chǎn)，每種價(jià)值的資產(chǎn)數(shù)量已知，請(qǐng)幫助心煩意亂的XHD夫婦計(jì)算一共有多少種分割資產(chǎn)的方法。

Input

輸入包含多個(gè)測(cè)試實(shí)例，每個(gè)實(shí)例的第一行是一個(gè)整數(shù)n(n<100)，表示一共有n種價(jià)值的資產(chǎn)，接著的n行每行包含兩個(gè)整數(shù)pi和mi(0<pi,mi<10)，分別表示某種價(jià)值和對(duì)應(yīng)的數(shù)量，n為0的時(shí)候結(jié)束輸入。

Output

對(duì)于每個(gè)測(cè)試實(shí)例，請(qǐng)輸出分割資產(chǎn)的方案數(shù)%10000，如果不能分割，請(qǐng)輸出“sorry”，每個(gè)實(shí)例的輸出占一行。

Sample Input

Sample Output

解析：起先是沒(méi)想到只是為了分割資金給wiskey而沒(méi)有除3，結(jié)果一直不正常。題意是要分割資金給一個(gè)人所以要除3，就是求能g夠組成總資金的1/3的組合數(shù)。思路很簡(jiǎn)單，直接上母函數(shù)模板

代碼：

#include<stdio.h>
int n,a[105],b[105],m;
int main()
{
    int i,j,k;
    while(~scanf("%d",&n),n)
    {
        m=0;
        int s[10010]={0},t[10010]={0};
        for(int i=0; i<n; i++)
        {
            scanf("%d%d",&a[i],&b[i]);
            m+=(a[i]*b[i]);
        }
        if(m%3!=0)
        {
            printf("sorry\n");
            continue;
        }
        m/=3;
        for(i=0; i<=b[0]&&i*a[0]<=m; i++)
        {
            s[i*a[0]]=1;
        }
        for(i=1; i<n; i++)
        {
            for(j=0; j<=m; j++)
                for(k=0; k<=b[i]&&k*a[i]+j<=m; k++)
                {
                    t[k*a[i]+j]+=s[j];
                    t[k*a[i]+j]%=10000;
                }
                for(j=0; j<=m; j++)
                {
                    s[j]=t[j];
                    t[j]=0;
                }
        }
        if(s[m]!=0)
            printf("%d\n",s[m]);
        else
            printf("sorry\n");
    }
    return 0;
}

hdu 2110 Crisis of HDU

Crisis of HDU