結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2020-09-22 11:00:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 3,154 bytes |
コンパイル時間 | 1,655 ms |
コンパイル使用メモリ | 174,472 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 09:55:51 |
合計ジャッジ時間 | 2,643 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#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」が条件を満たすこともあるので、初期値は -1int 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[10300] = {};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[10030] = {};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;}