結果

問題 No.3 ビットすごろく
ユーザー gunmanekogunmaneko
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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[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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0