結果

問題 No.3 ビットすごろく
コンテスト
ユーザー stack9996
提出日時 2015-08-25 16:31:27
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 653 bytes
コンパイル時間 535 ms
コンパイル使用メモリ 67,260 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-01 07:29:01
合計ジャッジ時間 1,497 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
#include <queue>

const int max = 10001;

int n;

int popCount(int n){
	int cnt = 0;
	while (n != 0){
		cnt += (n & 1 ? 1 : 0);
		n /= 2;
	}
	return cnt;
}

int bfs(){
	int map[max];
	for (int i = 0; i < max; ++i)map[i] = -1;
	map[1] = 1;
	std::queue<int> que;
	que.push(1);
	while (!que.empty()){
		int q = que.front();
		que.pop();
		int p = popCount(q);
		if (q - p >= 1 && map[q - p] == -1)map[q - p] = map[q] + 1, que.push(q - p);
		if (q + p <= n && map[q + p] == -1)map[q + p] = map[q] + 1, que.push(q + p);
	}
	return map[n];
}


int main(){
	std::cin >> n;
	std::cout << bfs() << std::endl;
	return 0;
}
0