結果
問題 | No.3 ビットすごろく |
ユーザー |
|
提出日時 | 2019-08-01 22:19:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 15 ms / 5,000 ms |
コード長 | 750 bytes |
コンパイル時間 | 2,111 ms |
コンパイル使用メモリ | 197,524 KB |
最終ジャッジ日時 | 2025-01-07 10:30:55 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;int popcnt(int n) {int cnt = 0;while (n) {cnt += n & 1;n /= 2;}return cnt;}int main() {int n;cin>>n;int dist[n+1];fill(dist, dist+n+1, -1);dist[1] = 1;queue<int> q;q.emplace(1);while (!q.empty()) {int now = q.front();q.pop();int move = popcnt(now);if (1 <= now-move && dist[now-move] == -1) {dist[now-move] = dist[now] + 1;q.push(now-move);}if (now+move <= n && dist[now+move] == -1) {dist[now+move] = dist[now] + 1;q.push(now+move);}}cout << dist[n] << endl;return 0;}