結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2017-04-29 14:59:47 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 601 bytes |
コンパイル時間 | 1,132 ms |
コンパイル使用メモリ | 29,696 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-01 08:40:45 |
合計ジャッジ時間 | 1,208 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include<stdio.h> #include<string.h> int r[10000+1], n; int bitcount(int x) { int ret=0; for(;x;x>>=1) { if(x&1) ret++; } return ret; } int min_u(int* m, int x) { if(*m==-1 || *m>x) { *m=x; return 1; } return 0; } void solve(int x, int t) { int nx, b; if(x==n) return; b=bitcount(x); nx=x+b; if(1<=nx && nx<=n && min_u(&r[nx], t+1)) solve(nx, t+1); nx=x-b; if(1<=nx && nx<=n && min_u(&r[nx], t+1)) solve(nx, t+1); } int main(void) { while(scanf("%d", &n)==1) { memset(r, 255, sizeof(r)); min_u(&r[1], 1); solve(1, 1); printf("%d\n", r[n]); } return 0; }