あなたはk個のそっくりな水球を持っていて、1つのn階の建物の上でテストを行って、あなたは水球が最低何階から下に投げて水球を破ることができることを知りたいです。水球がちょうど破れた最低階を測定するために、水球を最小限に抑えたいと思っています。(水球は最上階でも破れないかもしれません)任意の階で水球を捨ててテストすることができます。水球が破れていない場合は、それを続けて使用することができます。入力された各行には複数のテストが含まれ、各テストは1行です。各試験セットは、2つの整数kおよびnを含み、1<=k<=100であり、nは64ビットの整数である。各テストについて、出力が最悪の場合、水球がフロアを破る最小回数を測定した。63回を超えると「More than 63 trials needed.」>63回の場合は考慮しないので、考慮すべき部分に用いられる球の個数も63を超えず、f(i,j)状態でi個の風船を用い、j回を投げて最大で決定できる層数を表す。では、dp[i][j]=dp[i-1][j-1]+dp[i][j-1]+1; //Serene //紫書p 292水の入った風船Dropping water balloons #include #include #include #include #include #include using namespace std; int k; unsigned long long n,dp[70][70]; int main() { scanf("%d%lld",&k,&n); int ansi,ansj;bool ok; while(k) { memset(dp,0,sizeof(dp)); ansi=ansj=64;ok=0; for(int i=1;i<=64&&i<=k;++i){ for(int j=1;j<64;++j) { dp[i][j]=dp[i-1][j-1]+dp[i][j-1]+1; if((i==k||i>=63)&&dp[i][j]>=n) { ansi=i;ansj=j; ok=1;break; } } if(ok) break; } if(ansi==64||ansj==64) { printf("More than 63 trials needed."); } else printf("%d",ansj); scanf("%d%lld",&k,&n); } return 0; }