結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2020-08-24 21:32:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 220 ms / 5,000 ms |
コード長 | 729 bytes |
コンパイル時間 | 1,541 ms |
コンパイル使用メモリ | 166,552 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 09:53:53 |
合計ジャッジ時間 | 5,148 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include<bits/stdc++.h> #define rep(i,N) for(ll (i)=0;(i)<(N);(i)++) #define chmax(x,y) x=max(x,y) #define chmin(x,y) x=min(x,y) using namespace std; typedef long long ll; typedef pair<int,int> P; const int mod = 1000000007; const int INF = 1001001001; int dp[10010]; int n; int countOne(int x) { int res = 0; while (x > 0) { res += x&1; x = x>>1; } return res; } void dfs(int x, int depth=0) { if (x <= 0 || x > n) return; if (dp[x] <= depth) return; dp[x] = depth; int nums = countOne(x); dfs(x - nums, depth + 1); dfs(x + nums, depth + 1); return; } int main() { cin >> n; rep(i, n + 1) dp[i] = INF; dfs(1, 1); int ans = dp[n]; if (ans == INF) ans = -1; cout << ans << endl; }