Submission #29615

ソースコード

#include <bits/stdc++.h>
#define outl(x) cout << (x) << '\n'
#define FAST() cin.tie(0), ios::sync_with_stdio(false)
using namespace std;
 
const int INF = 1 << 29;
int N;
int d[10005];
 
int bfs(){
  queue<int> q;
  q.push(1);
  fill_n(d, 10005, INF);
  d[1] = 1;
 
  while(!q.empty()){
    const int t = q.front();q.pop();
    if(t == N)return(d[t]);
 
    const int p = __builtin_popcount(t);
    if(t + p <= N && d[t]+1 < d[t+p]){
      q.push(t+p);
      d[t+p] = d[t] + 1;
    }
    if(t - p > 0 && d[t]+1 < d[t-p]){
      q.push(t-p);
      d[t-p] = d[t] + 1;
    }
  }
  return(-1);
}
 
main()
{
  FAST();
  cin >> N;
  outl( bfs() );
}

ステータス

項目	データ
問題	0288 - ビットすごろく
ユーザー名	Arumakan_ei1727
投稿日時	2017-12-11 18:19:01
言語	C++
状態	Accepted
得点	2
ソースコード長	677 Byte
最大実行時間	24 ms
最大メモリ使用量	788 KB

セット

	セット	得点	Cases
1	ALL	2 / 2	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
1.txt	AC	23 ms	480 KB	1
2.txt	AC	22 ms	568 KB	1
3.txt	AC	15 ms	656 KB	1
4.txt	AC	17 ms	696 KB	1
5.txt	AC	19 ms	740 KB	1
6.txt	AC	24 ms	520 KB	1
7.txt	AC	14 ms	560 KB	1
8.txt	AC	18 ms	608 KB	1
9.txt	AC	18 ms	656 KB	1
10.txt	AC	17 ms	400 KB	1
11.txt	AC	16 ms	444 KB	1
12.txt	AC	17 ms	488 KB	1
13.txt	AC	13 ms	536 KB	1
14.txt	AC	18 ms	572 KB	1
15.txt	AC	20 ms	488 KB	1
16.txt	AC	20 ms	404 KB	1
17.txt	AC	17 ms	444 KB	1
18.txt	AC	19 ms	608 KB	1
19.txt	AC	22 ms	520 KB	1
20.txt	AC	16 ms	612 KB	1
challenge01.txt	AC	18 ms	704 KB	1
challenge02.txt	AC	16 ms	744 KB	1
challenge03.txt	AC	21 ms	788 KB	1
system_test1.txt	AC	18 ms	700 KB	1
system_test2.txt	AC	18 ms	740 KB	1
system_test3.txt	AC	23 ms	528 KB	1
system_test4.txt	AC	19 ms	568 KB	1