結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2020-06-17 22:05:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 191 ms / 5,000 ms |
コード長 | 578 bytes |
コンパイル時間 | 1,553 ms |
コンパイル使用メモリ | 167,720 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-01 09:50:45 |
合計ジャッジ時間 | 4,745 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> P; ll n; ll ans[10005]; void solve(ll i){ ll c=0,j=i; while(j>0){ c=c+j%2; j=j/2; } if(i-c>=1&&ans[i-c]>ans[i]+1){ ans[i-c]=ans[i]+1; solve(i-c); } if(i+c<=n&&ans[i+c]>ans[i]+1){ ans[i+c]=ans[i]+1; solve(i+c); } } int main(void){ cin>>n; ans[1]=1; for(int i=2;i<=n;i++){ ans[i]=1000000000; } solve(1); if(ans[n]==1000000000){ ans[n]=-1; } cout<<ans[n]<<endl; }