Submission #28339

ソースコード

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int getbit(int n){
  int ans=0;
  while(1){
    ans+=n%2;
    n/=2;
    if(n==0)
      break;
  }
  return ans;
}
int main(){
  int n;
  queue<int>que;
  int dp[10001];
  int mp[10001];
  int d[]={-1,1};
  memset(dp,-1,sizeof(dp));
  cin >> n;
  dp[1]=1;
  que.push(1);
  for(int i=1;i<=n;i++)
    mp[i]=getbit(i);
  while(!que.empty()){
    int now=que.front();
    que.pop();
    if(now==n)
      break;
    for(int i=0;i<2;i++){
      int next=now+mp[now]*d[i];
      if(next>=1&&next<=n&&dp[next]==-1){
        dp[next]=dp[now]+1;
        que.push(next);
      }
    }
  }
  cout << dp[n] << endl;
  return 0;
}

ステータス

項目	データ
問題	0288 - ビットすごろく
ユーザー名	ei1710
投稿日時	2017-11-03 20:08:26
言語	C++
状態	Accepted
得点	2
ソースコード長	730 Byte
最大実行時間	68 ms
最大メモリ使用量	724 KB

セット

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

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
1.txt	AC	68 ms	480 KB	1
2.txt	AC	21 ms	488 KB	1
3.txt	AC	20 ms	580 KB	1
4.txt	AC	16 ms	636 KB	1
5.txt	AC	15 ms	676 KB	1
6.txt	AC	17 ms	472 KB	1
7.txt	AC	22 ms	628 KB	1
8.txt	AC	17 ms	544 KB	1
9.txt	AC	13 ms	596 KB	1
10.txt	AC	21 ms	404 KB	1
11.txt	AC	13 ms	436 KB	1
12.txt	AC	25 ms	464 KB	1
13.txt	AC	18 ms	492 KB	1
14.txt	AC	19 ms	532 KB	1
15.txt	AC	21 ms	584 KB	1
16.txt	AC	15 ms	612 KB	1
17.txt	AC	20 ms	384 KB	1
18.txt	AC	18 ms	540 KB	1
19.txt	AC	20 ms	440 KB	1
20.txt	AC	16 ms	548 KB	1
challenge01.txt	AC	18 ms	636 KB	1
challenge02.txt	AC	18 ms	664 KB	1
challenge03.txt	AC	17 ms	688 KB	1
system_test1.txt	AC	18 ms	592 KB	1
system_test2.txt	AC	16 ms	624 KB	1
system_test3.txt	AC	16 ms	676 KB	1
system_test4.txt	AC	16 ms	724 KB	1