Submission

Score: 70

User: Kidmaiok

Problemset: Croissaria Number

Language: cpp

Time: 0.927 second

Submitted On: 2025-10-05 11:40:32

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

string s;
ll dp[20][10][2][2]; // pos, first_digit, tight, leading_zero
// -1 คือยังไม่คำนวณ

ll dfs(int pos, int first_digit, bool tight, bool leading_zero) {
    if (pos == (int)s.size()) {
        // เลขต้องมีอย่างน้อย 2 หลัก (ไม่ใช่เลขนำ 0 ทั้งหมด)
        return (first_digit != 0 && !leading_zero) ? 1 : 0;
    }
    ll &res = dp[pos][first_digit][tight][leading_zero];
    if (res != -1) return res;
    res = 0;
    int limit = tight ? (s[pos] - '0') : 9;

    for (int dig = 0; dig <= limit; dig++) {
        if (leading_zero) {
            // ยังไม่ได้เลือกหลักแรกจริง
            // เลือก dig = 0 จะยังเป็น leading_zero = true
            // เลือก dig > 0 จะเป็น first digit = dig
            if (dig == 0) {
                // ข้าม เลขนำ 0
                res += dfs(pos + 1, 0, tight && (dig == limit), true);
            } else {
                // เลือกหลักแรก
                res += dfs(pos + 1, dig, tight && (dig == limit), false);
            }
        } else {
            // เลือกหลักต่อไป ต้องน้อยกว่า first_digit
            if (dig < first_digit) {
                res += dfs(pos + 1, first_digit, tight && (dig == limit), false);
            }
        }
    }
    return res;
}

ll countCroissaria(ll X) {
    if (X < 10) return 0; // เลข Croissaria ต้อง ≥ 10

    s = to_string(X);
    memset(dp, -1, sizeof(dp));
    return dfs(0, 0, true, true);
}

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

    int T; cin >> T;
    while (T--) {
        ll L, R; cin >> L >> R;
        ll ans = countCroissaria(R) - countCroissaria(L - 1);
        cout << ans << "\n";
    }
    return 0;
}