結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2017-10-05 10:00:05 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 1,400 bytes |
コンパイル時間 | 783 ms |
コンパイル使用メモリ | 87,244 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 08:49:37 |
合計ジャッジ時間 | 1,701 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <iostream> #include <vector> #include <string> #include <cstring> #include <math.h> #include <cmath> #include <limits.h> #include <map> #include <set> #include <queue> #include <algorithm> #include <functional> #include <stdio.h> using namespace std; long long MOD = 1000000007; int bitcount( int a ) { int ret = 0; for ( int i = 0; (1 << i ) <= a; i++ ) { if ((1<<i) & a) { ret++; } } return ret; } int main() { int N; cin >> N; vector< vector<int> > path(N+1); vector<int> dist(N+1); fill( dist.begin(), dist.end(), -1 ); dist[1] = 1; for ( int i = 1; i <= N; i++ ) { int b = bitcount(i); if ( i+b <= N ) { path[i].push_back(i+b); } if ( i-b >= 1 ) { path[i].push_back(i-b); } } queue<int> Q; for ( int i = 0; i < path[1].size(); i++ ) { Q.push( path[1][i] ); dist[path[1][i]] = dist[1]+1; } while ( !Q.empty() ) { int c = Q.front(); Q.pop(); if ( c == N ) { break; } for ( int i = 0; i < path[c].size(); i++ ) { if ( dist[path[c][i]] == -1 ) { Q.push( path[c][i] ); dist[path[c][i]] = dist[c]+1; // cout << dist[path[c][i]] << endl; } } } cout << dist[N] << endl; return 0; }