Submission #41111

ソースコード

?
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
#include<bits/stdc++.h>
#define FOR(i,n) for(int i=0;i<n;i++)
#define SFOR(i,a,b) for(int i=a;i<b;i++)
#define INF INT_MAX
#define F first
#define S second
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int n,memo[100002];
P now;
queue<P>q;
int conv(int m){
int r=m;
if(memo[m]!=0) return memo[m];
int ans=0;
while(m>1){
if(m%2==1) ans++;
m/=2;
}
if(m==1) ans++;
return memo[r]=ans;
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
cin>>n;
q.push(P(1,0));
while(!q.empty()){
now=q.front(); q.pop();
if(now.F==n) break;
int ne=conv(now.F);
if(now.F+ne<=n && memo[now.F+ne]==0) q.push(P(now.F+ne,now.S+1));
if(now.F-ne>=1 && memo[now.F-ne]==0) q.push(P(now.F-ne,now.S+1));
}
if(now.F==n){
cout<<now.S+1<<endl;
}else{
cout<<"-1"<<endl;
}
return 0;
}

ステータス

項目 データ
問題 0288 - ビットすごろく
ユーザー名 Zzz..ei1704..Zzz
投稿日時 2018-08-10 10:56:10
言語 C++14
状態 Accepted
得点 2
ソースコード長 906 Byte
最大実行時間 153 ms
最大メモリ使用量 3392 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
1.txt AC 22 ms 480 KB
1
2.txt AC 24 ms 552 KB
1
3.txt AC 25 ms 676 KB
1
4.txt AC 18 ms 636 KB
1
5.txt AC 18 ms 580 KB
1
6.txt AC 30 ms 532 KB
1
7.txt AC 24 ms 536 KB
1
8.txt AC 21 ms 604 KB
1
9.txt AC 18 ms 676 KB
1
10.txt AC 40 ms 1076 KB
1
11.txt AC 69 ms 1288 KB
1
12.txt AC 34 ms 864 KB
1
13.txt AC 24 ms 628 KB
1
14.txt AC 28 ms 508 KB
1
15.txt AC 68 ms 1360 KB
1
16.txt AC 132 ms 2748 KB
1
17.txt AC 91 ms 1352 KB
1
18.txt AC 130 ms 2608 KB
1
19.txt AC 21 ms 608 KB
1
20.txt AC 147 ms 3328 KB
1
challenge01.txt AC 63 ms 1376 KB
1
challenge02.txt AC 152 ms 3392 KB
1
challenge03.txt AC 153 ms 3308 KB
1
system_test1.txt AC 133 ms 2720 KB
1
system_test2.txt AC 32 ms 668 KB
1
system_test3.txt AC 21 ms 748 KB
1
system_test4.txt AC 84 ms 1344 KB
1