問題はこちら
No.313 π - yukicoder
円周率を20万桁目まで正しく計算するプログラムを書く問題……ではない
「0~9の各数字が何回登場するか」がわかれば、どこの値が間違っているかわかる
幸いsample1.txtに、整数部以外の20万桁は正しいものがおいてあるので、これを保存して数える
int main(){ int i,p,q int a[10]={20104,20063,19892,20011,19874,20199,19898,20163,19956,19841}; //a[i]はiが登場する回数 char s[200010]; gets(s); for(i=0;s[i];i++)if(i!=1)a[i-'0']--; for(i=0;;i++)if(a[i]==-1){p=i;break;} //a[i]==-1⇔iの登場が1回多い for(i=0;;i++)if(a[i]==1){q=i;break;} //a[i]==1⇔iの登場が1回少ない printf("%d %d",p,q); return 0; }
うん長い…。とくにaの配列
「正しい」「1多い」「1少ない」さえ判別できればいいのだから、3での剰余を保存しとけば十分じゃね?
a[10]={1,2,2,1,2,0,2,0,0,2},j; main(i){ for(;read(0,&i,1);)i>47&&a[i-48]--; for(;i=a[j]%3+2;j++); for(;~a[i]%3;i++); j=!printf("%d %d",i,j); }
他の剰余も試してみよう。5で割ると後ろ2つが1になるから、保存する値を1ずらせば省略できる
a[10]={3,2,1,0,3,3,2,2},j; main(i){ for(;read(0,&i,1);)i>47&&a[i-48]--; for(;i=a[j]%5;j++); for(;a[i]%5+2;i++); j=!printf("%d %d",i,j); }
読み込み部分は '.' bitand 15 が14になることを使えばa[i&15]--と略せる
また読み込み終了時にi≧48であることを使うと
a[99]={3,2,1,0,3,3,2,2},j; main(i){ for(;read(0,&i,1);)a[i&15]--; for(;a[j]%5;j++); for(;a[--i]%5+2;); //a[14]は-1になっているので影響を与えない j=!printf("%d %d",i,j); }
これにループ圧縮を施して
a[99]={3,2,1,0,3,3,2,2},j; main(i){ for(;read(0,&i,1)?a[i&15]--,1:a[j]%5?++j:a[--i]%5+2;); j=!printf("%d %d",i,j); }
112B
2016/10/20追記
decじゃなくてincにすれば,1が省略できる
さらに最後の出力をfor文の中に放り込んでもREにはならないらしい
a[99]={2,3,4,0,2,2,3,3},j; main(i){for(;read(0,&i,1)?++a[i&15]:a[j]%5?++j:a[--i]%5-2?:!printf("%d %d",i,j););}
109B
2017/07/25追記
配列サイズをごまかして1B短縮
コンパイラのバージョンアップによる2Bと合わせて3B短縮
a[9]={2,3,4,0,2,2,3,3},j; main(i){for(;read(0,&i,1)?++a[i&15]:a[j]%5?++j:a[--i]%5-2;);printf("%d %d",i,j);}
106B