Submission #29614

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
//_____
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
#define rep(i,n) for(int i=0; i<(n); ++i)
#define reps(i,f,n) for(int i=(f); i<=(n); ++i)
#define show(x) cerr << #x << ':' << x << endl
#define outl(x) cout << (x) << '\n'
#define FAST() cin.tie(0), ios::sync_with_stdio(false)
using namespace std;
template<class A, class B>inline bool chmax(A &a, B b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, B b){return b<a ? a=b,1 : 0;}
typedef long long ll;
typedef pair<int,int> Pii;
//_______
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()){
int t = q.front();q.pop();
if(t == N)return(d[t]);
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:16:39
言語 C++
状態 Accepted
得点 2
ソースコード長 1120 Byte
最大実行時間 35 ms
最大メモリ使用量 924 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
1.txt AC 30 ms 604 KB
1
2.txt AC 18 ms 576 KB
1
3.txt AC 18 ms 668 KB
1
4.txt AC 27 ms 580 KB
1
5.txt AC 24 ms 744 KB
1
6.txt AC 18 ms 792 KB
1
7.txt AC 23 ms 704 KB
1
8.txt AC 27 ms 748 KB
1
9.txt AC 18 ms 788 KB
1
10.txt AC 18 ms 524 KB
1
11.txt AC 27 ms 696 KB
1
12.txt AC 23 ms 608 KB
1
13.txt AC 18 ms 652 KB
1
14.txt AC 21 ms 564 KB
1
15.txt AC 35 ms 480 KB
1
16.txt AC 21 ms 524 KB
1
17.txt AC 30 ms 568 KB
1
18.txt AC 18 ms 484 KB
1
19.txt AC 18 ms 660 KB
1
20.txt AC 17 ms 624 KB
1
challenge01.txt AC 18 ms 708 KB
1
challenge02.txt AC 15 ms 752 KB
1
challenge03.txt AC 21 ms 796 KB
1
system_test1.txt AC 26 ms 712 KB
1
system_test2.txt AC 23 ms 880 KB
1
system_test3.txt AC 18 ms 924 KB
1
system_test4.txt AC 29 ms 840 KB
1