HDU 2110 Crisis of HDU【親関数】
2573 ワード
Crisis of HDU
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3642 Accepted Submission(s): 1020
Problem Description
ところで、前回はHDU大戦の東洋小苟といえば、結果的に中国側が大勝したのは当然で、この戦いも海東グループの世界の同業界における地位をさらに強固にした.グループの発展に従って、多くの創業時期の元老は次第に功成して退いて、まず8600移民の海外で、それからlinle夫婦は山林を退いて、次第に、最初の多くの元老はXHD夫婦とWiskeyの3人しか残っていません.
2020年になると、拡張過剰に加えてネズミの数が年々減少し、会社の発展はかつてない危機に直面し、この時グループには流動資金がなく、さらに恐ろしいことに、この時、wiskeyも脱退することにした.
脱退自体は面倒ではありません.面倒なことに、脱退した人は相応の割合(1/3)の資産を引き出す必要があります.
会社がこの時点で合計n種類の価値を持つ資産を想定し、各価値の資産数が既知であると仮定し、心が乱れているXHD夫婦が合計何種類の資産を分割する方法を計算するのを助けてください.
Input
入力には複数のテストインスタンスが含まれ、各インスタンスの最初の行は1つの整数n(n<100)であり、合計n種類の価値を持つ資産を表し、次にn行の各行は2つの整数piとmi(0
Output
各テストインスタンスについては、分割資産のシナリオ数%10000を出力し、分割できない場合は「sorry」を出力し、各インスタンスの出力が1行を占めます.
Sample Input
Sample Output
/*
問題解:親関数の組合せ数を求める
*/
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3642 Accepted Submission(s): 1020
Problem Description
ところで、前回はHDU大戦の東洋小苟といえば、結果的に中国側が大勝したのは当然で、この戦いも海東グループの世界の同業界における地位をさらに強固にした.グループの発展に従って、多くの創業時期の元老は次第に功成して退いて、まず8600移民の海外で、それからlinle夫婦は山林を退いて、次第に、最初の多くの元老はXHD夫婦とWiskeyの3人しか残っていません.
2020年になると、拡張過剰に加えてネズミの数が年々減少し、会社の発展はかつてない危機に直面し、この時グループには流動資金がなく、さらに恐ろしいことに、この時、wiskeyも脱退することにした.
脱退自体は面倒ではありません.面倒なことに、脱退した人は相応の割合(1/3)の資産を引き出す必要があります.
会社がこの時点で合計n種類の価値を持つ資産を想定し、各価値の資産数が既知であると仮定し、心が乱れているXHD夫婦が合計何種類の資産を分割する方法を計算するのを助けてください.
Input
入力には複数のテストインスタンスが含まれ、各インスタンスの最初の行は1つの整数n(n<100)であり、合計n種類の価値を持つ資産を表し、次にn行の各行は2つの整数piとmi(0
Output
各テストインスタンスについては、分割資産のシナリオ数%10000を出力し、分割できない場合は「sorry」を出力し、各インスタンスの出力が1行を占めます.
Sample Input
2
1 1
2 1
0
Sample Output
1
， ？ XHD ？ ， ——
/*
問題解:親関数の組合せ数を求める
*/
#include<cstdio>
#include<cstring>
__int64 c1[10005],c2[10005],sum;
int main()
{
int n,i,j,k,a[102],b[102];
while(scanf("%d",&n)&&n)
{
sum=0;
for(i=1; i<=n; i++)
{
scanf("%d %d",&a[i],&b[i]);//a[i] ，b[i]
sum+=a[i]*b[i];
}
if(sum%3!=0) {printf("sorry
"); continue;}
sum/=3;
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
for(i=0; i<=b[1]*a[1]; i+=a[1])
{
c1[i]=1;
}
for(i=2; i<=n; i++)
{
for(j=0; j<=sum; j++)
{
if(c1[j])// 0MS, 15MS
for(k=0; k+j<=sum&&k/a[i]<=b[i]; k+=a[i])
{
c2[k+j]+=c1[j];
}
}
for(j=0; j<=sum; j++)
{
c1[j]=c2[j]%10000;
c2[j]=0;
}
}
if(c1[sum])
printf("%I64d
",c1[sum]%10000);
else printf("sorry
");
}
return 0;
}