結果

問題 No.3 ビットすごろく
ユーザー dgd1724dgd1724
提出日時 2016-10-04 18:44:14
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 135 ms / 5,000 ms
コード長 1,910 bytes
コンパイル時間 838 ms
コンパイル使用メモリ 103,716 KB
実行使用メモリ 4,696 KB
最終ジャッジ日時 2023-09-14 00:09:22
合計ジャッジ時間 3,275 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,384 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 5 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 3 ms
4,376 KB
testcase_09 AC 23 ms
4,376 KB
testcase_10 AC 55 ms
4,376 KB
testcase_11 AC 15 ms
4,376 KB
testcase_12 AC 5 ms
4,376 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 47 ms
4,376 KB
testcase_15 AC 116 ms
4,376 KB
testcase_16 AC 71 ms
4,380 KB
testcase_17 AC 107 ms
4,380 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 134 ms
4,504 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 49 ms
4,376 KB
testcase_23 AC 134 ms
4,696 KB
testcase_24 AC 135 ms
4,500 KB
testcase_25 AC 117 ms
4,376 KB
testcase_26 AC 1 ms
4,376 KB
testcase_27 AC 2 ms
4,376 KB
testcase_28 AC 66 ms
4,376 KB
testcase_29 AC 15 ms
4,376 KB
testcase_30 AC 2 ms
4,380 KB
testcase_31 AC 2 ms
4,376 KB
testcase_32 AC 10 ms
4,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:20:27: warning: overflow in conversion from ‘long int’ to ‘int’ changes value from ‘9999999999’ to ‘1410065407’ [-Woverflow]
 const static int de_MAX = 9999999999;
                           ^~~~~~~~~~

ソースコード

diff # 

#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