Submission #16460

ソースコード

#include<iostream>
#include<queue>
using namespace std;
typedef pair<int,int>P;
int bit(int n);
int main(){
  int n;
  int data[10005];
  bool flag[10005]={false};
  cin>>n;
  for(int i=1;i<=n;i++){
    data[i]=bit(i);
  }
  queue<P>que;
  flag[1]=true;
  que.push(P(data[1],1));
  while(!que.empty()&&que.front().first!=n){
    P p=que.front();que.pop();
    int now=p.first;
    int cnt=p.second;
    if(now+data[now]<=n&&flag[now+data[now]]==false){
      que.push(P(now+data[now],cnt+1));
      flag[now+data[now]]=true;
    }
    if(now-data[now]>0&&flag[now-data[now]]==false){
      que.push(P(now-data[now],cnt+1));
      flag[now-data[now]]=true;
    }
  }
  if(que.empty()){
    cout<<-1<<endl;
  }else{
    cout<<que.front().second<<endl;
  }
  return(0);
}
 
int bit(int n){
  int cnt=0;
  for(int i=0;i<15;i++){
    if((n&(1<<i))!=0){
      cnt++;
    }
  }
  return(cnt);
}

ステータス

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

セット

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

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
1.txt	AC	19 ms	480 KB	1
2.txt	AC	14 ms	600 KB	1
3.txt	AC	15 ms	484 KB	1
4.txt	AC	18 ms	584 KB	1
5.txt	AC	22 ms	412 KB	1
6.txt	AC	19 ms	508 KB	1
7.txt	AC	17 ms	576 KB	1
8.txt	AC	21 ms	536 KB	1
9.txt	AC	19 ms	500 KB	1
10.txt	AC	13 ms	568 KB	1
11.txt	AC	20 ms	500 KB	1
12.txt	AC	43 ms	428 KB	1
13.txt	AC	20 ms	500 KB	1
14.txt	AC	17 ms	444 KB	1
15.txt	AC	18 ms	528 KB	1
16.txt	AC	27 ms	588 KB	1
17.txt	AC	17 ms	648 KB	1
18.txt	AC	23 ms	708 KB	1
19.txt	AC	20 ms	516 KB	1
20.txt	AC	24 ms	556 KB	1
challenge01.txt	AC	20 ms	580 KB	1
challenge02.txt	AC	21 ms	636 KB	1
challenge03.txt	AC	16 ms	564 KB	1
system_test1.txt	AC	23 ms	628 KB	1
system_test2.txt	AC	20 ms	564 KB	1
system_test3.txt	AC	14 ms	656 KB	1
system_test4.txt	AC	23 ms	736 KB	1