#26278 (C++11) No.3 ビットすごろく

• 問題: No.3 ビットすごろく
• ユーザー: 158b
• 提出日時: 2015-05-12 12:21:48
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 1,455 bytes
• コンパイル時間: 602 ms
• コンパイル使用メモリ: 61,048 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-07-06 00:04:32
• 合計ジャッジ時間: 1,947 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	4 ms; 5,376 KB
testcase_04	WA	-
testcase_05	AC	13 ms; 5,376 KB
testcase_06	AC	5 ms; 5,376 KB
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	AC	13 ms; 5,376 KB
testcase_13	AC	3 ms; 5,376 KB
testcase_14	AC	27 ms; 5,376 KB
testcase_15	AC	41 ms; 5,376 KB
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	AC	1 ms; 5,376 KB
testcase_22	AC	28 ms; 5,376 KB
testcase_23	AC	43 ms; 5,376 KB
testcase_24	WA	-
testcase_25	WA	-
testcase_26	AC	2 ms; 5,376 KB
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-

ソースコード

#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
using namespace std;

int main(){
	//始まりの数値は１
	const int Max = 10000;
	int go[Max] = {0};
	int min[Max];
	int n;
	int least;
	
	cin >> n;
	
	//移動可能数算出
	for(int i=0; i<n; i++){
		least = i + 1;
		while(least > 0){
			if(least % 2 == 1){
				go[i] ++;
			}
			least /= 2;
		}
	}
	
	//min表初期化
	for(int i=0; i<n; i++){
		min[i] = 99999;
	}
	
	//移動最低数算出
	min[0] = 1;
	bool flg = false;
	int count = 0;	//スタックデータ数
	int stac[Max];
	int from = 0;
	
	//
	while(!flg){
		//現在地がゴールなら終了...ではない！！
		if(from == n - 1){
			break;
		}
		
		//先へ移動
		if(from + go[from] <= n - 1){
			if(min[from] + 1 < min[ from + go[from] ]){
				min[from + go[from]] = min[from] + 1;
				stac[count] = from + go[from];
				count ++;
			}
		}
		
		//前へ移動
		if(from - go[from] >= 0){
			if(min[from] + 1 < min[ from - go[from] ]){
				min[from - go[from]] = min[from] + 1;
				stac[count] = from - go[from];
				count ++;
			}
		}
		
		//スタック消化(スタックがなくなったら終了)
		if(count == 0){
			break;
		}else{
			count --;
			from = stac[count];
		}
	}
	
	//結果出力
	if(min[n-1] == 99999){
		cout << -1 << endl;
	}else{
		cout << min[n-1] << endl;
	}
	
	//全て出力
	/*
	cout << endl;
	for(int i=0; i<n; i++){
		cout << min[i] << endl;
	}
	*/
	
	return 0;
}