Bài C - Educational Codeforces Round 50 (Div.2)

Bài C:
Đề bài: Chúng ta gọi một vài số là classy nếu các chữ số trong hệ thập phân chứa không quá 3 số khác không. Ví dụ, số 4, 200000, 10203 là classy và các số 4231, 102306, 7277420000 là không phải.
Bạn được cho một đoạn [L;R]. Đếm số các số classy x thỏa mãn L<=x<=R.
Mỗi testcase chứa một vài segments, mỗi đoạn bạn được yêu cầu giải quyết lần lượt.
Đầu vào:
+ Dòng đầu tiên chứa 1 số nguyên T(1<=T<=10^4) - số segments trong testcase.
+ T dòng tiếp theo, mỗi dòng chứa hai số nguyên L(i) và R(i) (1<=L(i)<=R(i)<=10^(18)).
Đầu ra:
+ In ra T dòng, mỗi dòng là số các số classy trong đoạn [L(i),R(i)].
Ví dụ:
Đầu vào:
4
1 1000
1024 1024
65536 65536
999999 1000001
Đầu ra:
1000
1
0
2
Hướng dẫn:
Ở đây, chúng ta có hai cách tiếp cận bài toán:
Cách 1 - Dùng tổ hợp:
Vấn đề đặt ra: Đếm có bao nhiêu số đẹp tròn đoạn [L;R] chúng ta thường đếm trên đoạn [1;R] và [1;L-1] (hay [1;R+1) và [1;L) và trừ chúng lẫn nhau. Chúng tôi thử cách này dưới đây, đếm calc(R+1)-calc(L).
 Chúng ta hãy sửa một số tiền tố của các số biên dưới. Chúng ta muốn tính số lượng các số có cùng tiền tố nhưng nhỏ hơn chữ số tiếp theo. Nếu chúng ta tính nó cho tất cả các tiền tố (bao gồm tập rỗng), chúng ta sẽ có câu trả lời.
 Và điều này khá dễ. Chúng ta giả sử tiền số bao gồm k chữ số khác 0, chiều dài của hậu tố là x và chữ cái tiếp theo được chọn là d. Nếu d bằng 0 thì kết quả rõ ràng là 0. Ngược lại chúng ta có thể đặt 0 hoặc bất kì d-1 số khác không nào. thì vậy, ta có công thức tổng quát là: $\sum\limits_{i=0}^{3-k}\binom{x-1}{i}.9^i+(d-1).\sum\limits_{i=0}^{3-k-1}\binom{x-1}{i}.9^i$.
Chúng ta chọn vị trí i từ hậu tố để đặt số khác 0 vào chúng (bất kì số nào từ 1 đến 9) và lấp đầy các số còn lại là số 0.
Độ phức tạp chung là O(T.log(n)).
Cách 2- Ta tính trước:
Đây là một điều khá dễ để suy luận. Thật vậy, có khoảng 700000 số thỏa mãn, bạn có thể sinh tất cả chúng, đặt chúng vào mảng và sắp xếp lại theo thứ tự và dùng tìm kiếm nhị phân cho các truy vấn.
Độ phức tạp chung O(T.log ÁNSCNT).
Lời giải cách 1:

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

long long C[20][20];
long long pw[4];

long long cnk(int n, int k){
    if (k < 0 || k > n) return 0;
    return C[n][k];
}

long long get(int n, int lft){
    long long tot = 0;
    forn(i, lft + 1)
        tot += cnk(n, i) * pw[i];
    return tot;
}

long long calc(long long x){
    string s = to_string(x);
    
    long long res = 0;
    int cur = 3;
    int n = s.size();
    
    forn(i, n){
        if (s[i] == '0') continue;
        res += get(n - i - 1, cur);
        --cur;
        if (cur == -1) break;
        res += get(n - i - 1, cur) * (s[i] - '1');
    }
    
    return res;
}

int main() {
    forn(i, 20){
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j)
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    }
    pw[0] = 1, pw[1] = 9, pw[2] = 81, pw[3] = 729;
    int T;
    scanf("%d", &T);
    forn(i, T){
        long long L, R;
        scanf("%lld%lld", &L, &R);
        printf("%lld\n", calc(R + 1) - calc(L));
    }
    return 0;
}

Lời giải cách 2:

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

vector<long long> res;

void brute(int pos, int cnt, long long cur){
    if (pos == 18){
        res.push_back(cur);
        return;
    }
    
    brute(pos + 1, cnt, cur * 10);
    
    if (cnt < 3)
        for (int i = 1; i <= 9; ++i)
            brute(pos + 1, cnt + 1, cur * 10 + i);
}

int main() {
    brute(0, 0, 0);
    res.push_back(1000000000000000000);
    
    int T;
    scanf("%d", &T);
    forn(i, T){
        long long L, R;
        scanf("%lld%lld", &L, &R);
        printf("%d\n", int(upper_bound(res.begin(), res.end(), R) - lower_bound(res.begin(), res.end(), L)));
    }
    return 0;
}