結果

問題 No.3 ビットすごろく
コンテスト
ユーザー macle
提出日時 2020-03-27 00:00:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,856 bytes
コンパイル時間 1,586 ms
コンパイル使用メモリ 169,748 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-01-02 07:42:36
合計ジャッジ時間 2,684 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
 
//long long
using ll = long long;
 
// pair<int, int>
using PII = pair<int, int>;
 
//最大値、mod
const int MOD = 1000000007;
const int INF = 1000000000;
const long long LINF = 1e18;
const int MAX = 510000;
 
//出力系
#define print(x) cout << x << endl
#define prints(x) cout << fixed << setprecision(10) << x << endl
#define printc(x) cout << setw(2) << setfill('0') << x << endl;
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()
 
//for
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
 
//最大公約数 
unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
 
// 最小公倍数
unsigned lcm(unsigned a, unsigned b){
    return a / gcd(a, b) * b; 
}
 
// a = max(a, b), a = min(a, b)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 
// 階乗(MODをとる)
ll pow_mod(ll num, ll pow, ll mod) {
    ll prod = 1;
    num %= mod;
    while (pow > 0) {
        if (pow & 1) prod = prod * num % mod;
        num = num * num % mod;
        pow >>= 1;
    }
    return prod;
}
 
 
 
// 二項係数(MODとる、1 ≦ k ≦ n ≦ 10^7 程度)
// COMinit()
// COM(x, y)
// とコンビで使う
 
// テーブルを作る前処理
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;
}

int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};




vector<vector<int>> d(10,vector<int>(10, INF));

void wf(int n){
  REP(i, n)REP(j, n)REP(k, n){
    chmin(d[j][k], d[j][i] + d[i][k]);
  }
}

int solve(int i, int N){
  queue<pair<int, int>>que;
  que.push(make_pair(i, 1));
  bool flag[N] = {false};
  while(!que.empty()){
    int p = que.front().first;
    int d = que.front().second; 
    que.pop();
    if(N == p) return d;
    int a = p + __builtin_popcount(p);
    if(a > 0 && a <= N && flag[a] == false){
      que.push(make_pair(a , d + 1));
      flag[a] = true;
    }

    int b = p - __builtin_popcount(p);
    if(b > 0 && b <= N && flag[b] == false){
      que.push(make_pair(b, d + 1));
      flag[b] = true;
    }
  }
  return -1;
}


int main(){
  int N;
  cin >> N;
  cout << solve(1, N) << endl;
}
0