結果

問題 No.3 ビットすごろく
コンテスト
ユーザー dgd1724
提出日時 2016-10-04 18:44:14
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 202 ms / 5,000 ms
コード長 1,910 bytes
コンパイル時間 876 ms
コンパイル使用メモリ 108,820 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-01 08:06:57
合計ジャッジ時間 3,487 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:20:27: warning: overflow in conversion from ‘long int’ to ‘int’ changes value from ‘9999999999’ to ‘1410065407’ [-Woverflow]
   20 | const static int de_MAX = 9999999999;
      |                           ^~~~~~~~~~

ソースコード

diff #
raw source code 

#include <iostream>			//std::cout, std::cin
#include <string>			//std::string,std::to_string(C++11)
#include <vector>			//std::vector
#include <valarray>			//std::valarray
#include <algorithm>		//std::sort
#include <ctime>			//localtime_s
#include <cstdlib>			//abs
#include <cmath>			//abs,std::pow,sqrt,sin,cos,round,floor,ceil
#include <fstream>			//std::ifstream,std::ofstream
#include <iomanip>			//std::setprecision,std::setw,std::setfill
#include <random>			//std::random(C++11)
#include <numeric>			//std::accumulate
#include <functional>		//std::greater
#include <chrono>			//std::chrono(C++11)
#include <bitset>			//std::bitset
#include <queue>			//std::queue

const static double de_PI = 3.14159265358979323846;
const static int de_MOD = 1000000007;
const static int de_MAX = 9999999999;

int main(void) {

	//std::ifstream in("123.txt");	std::cin.rdbuf(in.rdbuf());
	//std::ofstream ofs("456.csv");
	//std::chrono::system_clock::time_point t_st = std::chrono::system_clock::now();

	int N = 0;
	std::cin >> N;
	std::vector<int> min(N + 1, de_MAX);
	std::vector<int> ans;
	std::queue<int> Q;
	Q.push(1);
	Q.push(0);

	int number = 0, ID = 0;

	while (1) {
		number++;
		while (1) {
			ID = Q.front();	Q.pop();
			if (ID == 0) { break; }
			min[ID] = number;
			if (ID == N) { ans.push_back(number);	continue; }
			int move = std::bitset<32>(ID).count();
			if (ID + move <= N && number + 1 < min[ID + move]) { Q.push(ID + move); }
			if (ID - move >= 1 && number + 1 < min[ID - move]) { Q.push(ID - move); }
		}
		if (Q.empty()) {
			break;
		}
		Q.push(0);
	}

	if (ans.empty()) {
		std::cout << -1 << std::endl;
	}
	else {
		std::cout << *std::min_element(ans.begin(), ans.end()) << std::endl;
	}

	//std::chrono::system_clock::time_point t_ed = std::chrono::system_clock::now();
	//std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(t_ed - t_st).count() << "ms" << std::endl;

}
0