結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2018-04-29 18:18:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 930 bytes |
コンパイル時間 | 656 ms |
コンパイル使用メモリ | 73,856 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-01 08:58:42 |
合計ジャッジ時間 | 1,650 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include<iostream> #include<queue> using namespace std; #define INF 10001; bool flag[10001]; int cnt[10001]; int bit(int x){ int res = 0; for(; x != 0; x &= x-1){ res++; } return res; } int main(){ int n; cin >> n; for(int i = 0; i < 10001; i++){ flag[i] = false; cnt[i] = INF; } cnt[1] = 1; queue<int> q; q.push(1); while(!q.empty()){ int now = q.front(); q.pop(); if(flag[now]) continue; flag[now] = true; int move = bit(now); if(now-move >= 1 && !flag[now-move]){ cnt[now-move] = min(cnt[now-move], cnt[now]+1); q.push(now-move); } if(now+move <= n && !flag[now+move]){ cnt[now+move] = min(cnt[now+move], cnt[now]+1); q.push(now+move); } } if(flag[n]) cout << cnt[n] << endl; else cout << -1 << endl; return 0; }