#556831 (C++14) No.3 ビットすごろく

• 問題: No.3 ビットすごろく
• ユーザー: gunmaneko
• 提出日時: 2020-09-22 10:56:54
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: RE
• 実行時間: -
• コード長: 3,152 bytes
• コンパイル時間: 1,771 ms
• コンパイル使用メモリ: 172,208 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-25 21:56:52
• 合計ジャッジ時間: 5,835 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
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	RE	-
testcase_04	AC	2 ms; 5,376 KB
testcase_05	RE	-
testcase_06	RE	-
testcase_07	WA	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	AC	2 ms; 5,376 KB
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	WA	-
testcase_19	RE	-
testcase_20	AC	2 ms; 5,376 KB
testcase_21	AC	2 ms; 5,376 KB
testcase_22	RE	-
testcase_23	RE	-
testcase_24	RE	-
testcase_25	RE	-
testcase_26	AC	2 ms; 5,376 KB
testcase_27	RE	-
testcase_28	RE	-
testcase_29	RE	-
testcase_30	AC	2 ms; 5,376 KB
testcase_31	AC	2 ms; 5,376 KB
testcase_32	RE	-

ソースコード

#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
const int MOD = 1000000007;

long long  fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y) {
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
/*逆元計算*/
long long int  modinv(long long a, long long m) {
	long long int b = m, u = 1, v = 0;
	while (b) {
		long long int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
// index が条件を満たすかどうか
vector<long long int >meguru;
bool isOK(int index, int key) {
	if (meguru[index] <= key) return true;
	else return false;
}
// 汎用的な二分探索のテンプレ
int binary_search(int key) {
	int left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
	int right = (int)meguru.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
	/* どんな二分探索でもここの書き方を変えずにできる！ */
	while (right - left > 1) {
		int mid = left + (right - left) / 2;

		if (isOK(mid, key)) left = mid;
		else right = mid;
	}
	/* left は条件を満たす最大の値、right は条件を満たさない最小の値になっている */
	return left;
}
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
double PI = 3.141592653589793238;
int main() {
	int n;
	cin >> n;
	int dp[1030] = {};
	for (int i = 1; i <= n; i++) {
		int a = i;
		while (a > 0) {
			if (a % 2 == 1) {
				dp[i]++;
			}
			a = a / 2;
		}
		//cout << dp[i] << endl;
	}
	queue<int>q;
	q.push(1);
	int susum[1030] = {};
	susum[1] = 1;
	while (q.size()) {
		int now = q.front();
		//cout << now << endl;
		q.pop();
		int b = dp[now];
		if (now == n) {
			cout << susum[now];
			return 0;
		}
		if (now - b > 0 && now - b <= n) {
			if (susum[now - b] == 0) {
				q.push(now - b);
				susum[now - b] = susum[now] + 1;
			}
		}
		if (now + b > 0 && now + b <= n) {
			if (susum[now + b] == 0) {
				q.push(now + b);
				susum[now + b] = susum[now] + 1;
			}
		}
	}
	cout << -1;
}