結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2016-12-23 02:07:19 |
言語 | C90 (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 1 ms / 5,000 ms |
コード長 | 746 bytes |
コンパイル時間 | 489 ms |
コンパイル使用メモリ | 20,992 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 08:12:25 |
合計ジャッジ時間 | 1,104 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
コンパイルメッセージ
main.c: In function ‘main’: main.c:59:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 59 | scanf("%d",&n); | ^~~~~~~~~~~~~~
ソースコード
#include<stdio.h> #define MAX 10000 #define INF 100000 int n,head=0,tail=0,queue[MAX]; int d[10001]; int used[10001]; int push(int x){ queue[tail]=x; tail++; } int pop(){ int x; x=queue[head]; head++; return x; } int bitcount(int x){ int i=0; while(x){ i+=x%2; x=x/2; } return i; } int bfs(int start){ int v=1,r; push(start); d[start]=1; used[start]=1; while(1){ if(head==tail)return -1; v=pop(); // printf("%d\n",v); if(v==n) return d[v]; r=bitcount(v); if(v+r<=n&&used[v+r]==0){ push(v+r); d[v+r]=d[v]+1; used[v+r]=1; } if(v-r>=0&&used[v-r]==0){ push(v-r); d[v-r]=d[v]+1; used[v-r]=1; } } } int main(){ int start=1; scanf("%d",&n); printf("%d",bfs(start)); return 0; }