結果

問題 No.491 10^9+1と回文
コンテスト
ユーザー Mister
提出日時 2020-05-29 18:30:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 20 ms / 1,000 ms
コード長 1,165 bytes
コンパイル時間 1,184 ms
コンパイル使用メモリ 81,648 KB
最終ジャッジ日時 2025-01-10 16:15:51
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 103
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using lint = long long;

std::vector<std::string> palis(int d) {
    std::vector<std::string> ret;

    if (d == 0) {
        ret.push_back("");

    } else if (d == 1) {
        for (int x = '0'; x <= '9'; ++x) {
            ret.push_back(std::string(1, x));
        }

    } else {
        auto res = palis(d - 2);
        for (auto& s : res) {
            s.insert(s.begin(), '$');
            s.push_back('$');
            for (int x = '0'; x <= '9'; ++x) {
                s.front() = s.back() = x;
                ret.push_back(s);
            }
        }
    }
    return ret;
}

void solve() {
    std::vector<int> ps;
    for (int d = 1; d <= 9; ++d) {
        auto res = palis(d);
        for (const auto& s : res) {
            if (s.front() == '0') continue;
            ps.push_back(std::stoi(s));
        }
    }

    lint n;
    std::cin >> n;
    n /= 1000000001;

    std::cout << std::count_if(ps.begin(), ps.end(), [&](auto p) { return p <= n; }) << "\n";
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    solve();

    return 0;
}
0