結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2018-08-29 13:56:41 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 398 ms / 5,000 ms |
コード長 | 782 bytes |
コンパイル時間 | 1,526 ms |
コンパイル使用メモリ | 167,776 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-01 09:06:08 |
合計ジャッジ時間 | 7,179 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define int long long #define INF 101010101 #define MAX 10000 int N, temp2[11000]; int huga(int a){ int ans=0; while(a){ if(a%2)ans++; a/=2; } return ans; } int foo(int a, int k){//cout<<a<<" "<<k<<" "<<temp2[a]<<endl;//int t;cin>>t; if(a==N)return k; int temp = huga(a), ans=INF; if(a-temp >= 1){ if(temp2[a-temp] > k){ temp2[a-temp] = k; ans = min(foo(a-temp,k+1), ans); } } if(a+temp <= N){ if(temp2[a+temp] > k){ temp2[a+temp] = k; ans = min(foo(a+temp,k+1), ans); } } return ans; } signed main(){ cin>>N; for(int i = 0; i <= MAX; i++)temp2[i]=INF; temp2[1]=1; int ans = foo(1,1); if(ans==INF)cout<<-1<<endl; else cout<<ans<<endl; return 0; }