結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2018-09-27 07:58:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 867 bytes |
コンパイル時間 | 1,661 ms |
コンパイル使用メモリ | 173,112 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 09:07:27 |
合計ジャッジ時間 | 2,623 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; int bin(int n) { int r = 0; while(n){ r += n % 2; n /= 2; } return r; } int main() { int n; cin >> n; vector<int> v(n+1,1); queue<int> que; que.push(1); while(que.size()){ int x = que.front(),y = bin(x); que.pop(); if(0 < x + y && x + y <= n && v[x+y] == 1){ que.push(x+y); v[x+y] = v[x] + 1; } if(x + y == n){ cout << v[x+y] << endl; return 0; } if(0 < x - y && x - y <= n && v[x-y] == 1){ que.push(x-y); v[x-y] = v[x] + 1; } if(x - y == n){ cout << v[x-y] << endl; return 0; } } cout << (n == 1 ? "1" : "-1") << endl; return 0; }