問題はこちら
No.250 atetubouのzetubou - yukicoder
互いに区別されるD個の箱に、ちょうどX個の玉をいれる場合の数に等しい
これは重複組合せで求める事ができ
となる
ところで最後の式の後ろからi項の部分積はもちろんなので整数であることから、整数の範囲で後ろから順番に計算していくことができる
また、そこに登場する各分数は(分子)-(分母)=X>0なので1より大きく、この部分積は単調増加だから、いったんTより大きくなったらそこで打ち切って良い
さらに、D,X≦1000、T≦10^15なので、64bitなら計算の途中でオーバーフローしない
int main(){ int q,d,x,i; long s,t; scanf("%d",&q); while(q--){ scanf("%d%d%ld",&d,&x,&t); s=1; for(i=1;i<d;i++){ s=s*(x+i)/i; if(s>t)break; } puts(s<=t?"AC":"ZETUBOU"); } return 0; }
ささっと縮める
long t,s; x,d; main(i){ for(gets(&i);s=~scanf("%d%d%ld",&d,&x,&t);puts(s>t?"ZETUBOU":"AC")) for(s=i=1;i<d&s<=t;s/=i++)s*=x+i; }
でループ圧縮したいなあと睨んでみた
for(gets(&i);s=i=scanf("%d%d%ld",&d,&x,&t)>0;puts(s>t?"ZETUBOU":"AC"))for(;i<d&s<=t;s/=i++)s*=x+i; //これではRE for(;i<d&s<2e15?s*=x+i,s/=i++:(i=scanf("%ld%d%d",&t,&d,&x)>0,i*s&&puts(s>t?"ZETUBOU":"AC"),s=i);); //ループ圧縮してみた for(;s=i<d&s<2e15?s*(x+i)/i++:(i=scanf("%ld%d%d",&t,&d,&x)>0,i*s&&puts(s>t?"ZETUBOU":"AC"),i);); //sへの代入をくくりだした for(;s=i>=d|s>2e15?i=scanf("%ld%d%d",&t,&d,&x)>0,i*s&&puts(s>t?"ZETUBOU":"AC"),i:s*(x+i)/i++;); //三項演算子の真偽を入れ替えてカッコを外した
途中を全部投げたわけではないのでわからないけれど、
//下から二番目 long t,s;x,d;main(i){for(;s=i<d&s<2e15?s*(x+i)/i++:(i=scanf("%ld%d%d",&t,&d,&x)>0,i*s&&puts(s>t?"ZETUBOU":"AC"),i););} //↑RE ↓AC long t,s;i,d;main(x){for(;s=i>=d|s>2e15?i=scanf("%ld%d%d",&t,&d,&x)>0,i*s&&puts(s>t?"ZETUBOU":"AC"),i:s*(x+i)/i++;);} //一番下
となって、REになったりならなかったりするのがよくわからない
117B
2017/06/18追記
自明な2Bと、gccのバージョンアップによるmainの返り値が不問になったことによる1Bで計3B短縮
long t,s;i,d;main(x){for(;s=i>=d|s>2e15?i=scanf("%ld%d%d",&t,&d,&x)>0,i*s&&puts(s>t?"ZETUBOU":"AC"),i:s*(x+i)/i++;);} //↓ long t,s;x;main(d,i){for(;s=i/d|s>2e15?i=scanf("%ld%d%d",&t,&d,&x)>0,i*s&&puts(s>t?"ZETUBOU":"AC"),i:s*++x/i++;);}
114B