問題はこちら
No.294 SuperFizzBuzz - yukicoder
整数が3の倍数である必要十分条件は、各位の和が3の倍数であること。
5の倍数である必要十分条件は、一の位が0or5であること。
これより、問題は「各位の数字が'3'or'5'で、1の位が5であり、'5'の個数が3の倍数であるようなものの内~」と読める
各桁の数は3か5なのでbitで保存出来そうな気がするが、それだと何桁の数かわからなくなる
(3を0、5を1で表すとすると「3335」→「0001」と「335」→「001」の区別がつかない)
ということで、最上位に番兵をつけ次のように変換する
3335→10001
5335→11001
335→ 1001
サンプルにある最大ケースが25桁なのでbitにすればそのまま保存できる
int main(){ int i,j,n; scanf("%d",&n); i=1; while(n){ i+=2; if(__builtin_popcount(i)%3==1)n--; //最上位に番兵がいるので、それをあわせて3の倍数+1になっていればよい } for(j=31;j>=0;j--){ n=i>>j; if(n>1)putchar(n%2?'5':'3'); //上位から0か1か調べる。出力は番兵以降 } return 0; }
これを縮めて
n,j=31; main(i){ for(scanf("%d",&n);n-=__builtin_popcount(i+=2)%3==1;); for(;j--;)(n=i>>j)>1&&putchar(51+n%2*2); exit(0); }
118B
exit(0)をつけないとRE、悲しい
(2016/05/29追記)
for文に空きがあるんだからカッコを付けないほうが短い
n,j=31; main(i){ for(scanf("%d",&n);n-=__builtin_popcount(i+=2)%3==1;); for(;j--;n>1&&putchar(51+n%2*2))n=i>>j; exit(0); }
117B