結果

問題 No.3 ビットすごろく
コンテスト
ユーザー ser
提出日時 2017-08-17 00:18:38
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 998 bytes
コンパイル時間 607 ms
コンパイル使用メモリ 69,440 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-01 08:47:39
合計ジャッジ時間 1,514 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:21:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   21 |     scanf("%d", &first_n);
      |     ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <limits>
#include <queue>

using namespace std;

int count_bit(uint32_t n) {
    int c = 0;
    while(n) {
        if(n&0x01) c++;
        n >>= 1;
    }
    return c;
}

int main() {
    int first_n;
    scanf("%d", &first_n);

    vector<int> costs(first_n+1, numeric_limits<int>::max());
    costs[1] = 1;

    queue<int> q;
    q.push(1);

    while(!q.empty()) {
        int n = q.front();
        q.pop();

        int bc = count_bit(n);

        if(n + bc == first_n) {
            costs[n+bc] = costs[n] + 1;
            break;
        }

        if(n + bc < first_n && costs[n] + 1 < costs[n+bc]) {
            costs[n+bc] = costs[n] + 1;
            q.push(n+bc);
        }

        if(n - bc >= 1 && costs[n] + 1 < costs[n-bc]) {
            costs[n-bc] = costs[n] + 1;
            q.push(n-bc);
        }
    }

    printf("%d\n", costs[first_n]==numeric_limits<int>::max() ? -1 : costs[first_n]);
}
0