Baroibeo Number

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
PhanDinhKhoi
Dạng bài
Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Trong một lần stream, thầy Ba nhận được \(100\)$ donate với câu hỏi từ HUYFBOY

“ Đố thầy viết được chương trình, nhập vào \(L\), \(R\) rồi đếm từ \(L\) đến \(R\) có bao nhiêu số Baroibeo. Nếu không làm được , thầy phải refund lại \(100\)$ “

Bạn hãy giúp thầy Ba làm thử thách trên. Nếu bạn làm được thầy Ba sẽ chia cho bạn \(50\)$.

• Số Baroibeo là 1 số tự nhiên mà số chữ số khác 0 của nó phải nhỏ hơn hoặc bằng 3.

VD: 4,10,99,707,4056,700007 là những số Baroibeo.

2345,56078,55555,1110001 không phải là số Baroibeo.

Input

  • Dòng đầu tiên bao gồm số nguyên dương \(T (T \leq 10)\) – Là số test

  • \(T\) dòng tiếp theo, dòng thứ \(i\) chứa 2 số nguyên dương \(L_i, R_i (L_i \leq R_i \leq 10^{18})\)

Các số trên một dòng của input file được ghi cách nhau bởi dấu cách

Output

  • Gồm \(T\) dòng – dòng thứ \(i\) là số lượng số Baroibeo trong đoạn \([Li,Ri]\)

Scoring

  • Subtask \(1\) (\(60\%\) số điểm): \(L_i \leq R_i \leq 10^6\)
  • Subtask \(2\) (\(40\%\) số điểm): \(L_i \leq R_i \leq 10^{18}\)

Example

Test 1

Input 
4
1 1000
1024 1024
65536 65536
999999 1000001
Output 
1000
1
0
2

Bình luận


  • 0
    MinhSharingan    8:05 p.m. 17 Tháng 3, 2021

    a anh ba


    • 0
      SPyofgame    6:55 p.m. 9 Tháng 6, 2020 ← chỉnh sửa 6

      Spoiler Alert

      Hint 1

      Duyệt và thử qua các số. Tăng biến đếm khi thỏa mãn

      Hint 2

      Thay vì duyệt các số và tăng giá trị số đó dần. Ta thử duyệt qua từng chữ số và ráp nó lại thành một số hoàn chỉnh để kiểm tra

      Hint 3

      Thử xây từng chữ số với các độ sâu.

      Gọi cnt là số lượng chữ số khác 0

      Gọi isLess để kiểm tra nếu số đó đã nhỏ hơn Ri

      Gọi isGreater để kiểm tra nếu số đó đã lớn hơn Li

      Hint 4

      Gọi f(x) là số số không âm thỏa mãn bé hơn x

      Có result = f(r) - f(l - 1)

      Lúc này ta chỉ cần kiểm tra hai lần việc isLess với Ri và Li - 1.

      Bỏ biến isGreater vì số đang được xây từng chữ số luôn không âm

      Reference AC code | \(O(n * 3 * 2)\) time | \(O(n)\) auxiliary space | DP_digit, DP_count

      C++
      int n;
vector<int> a;
vector<vector<vector<ll> > > f;
ll magic(int i = 0, int cnt = 0, bool isLess = false) /// Đệ quy có nhớ
{
    if (cnt > 3) return false;   /// Nếu số không thỏa mãn
    if (i >= n) return cnt <= 3; /// Nếu đã xây hết số, kiểm tra nếu số thỏa mãn

    ll &res = f[i][cnt][iln];  /// Dùng con trỏ &res để tiện mắt
    if (res != -1) return res; /// Nếu đã tính toán thì xuất
    res = 0;                   /// Ngược lại reset giá trị

    /// Cận dưới (lim) = 9 khi số đã bé hơn n, ngược lại là a[i]
    int lim = isLess ? 9 : a[i];
    for (int d = 0; d <= lim; ++d) /// Duyệt qua từng chữ số
        res += magic(i + 1, cnt + (d != 0), isLess || (d < lim)); /// Đệ quy độ sâu tiếp theo

    return res;
}

vi convert(ll n) /// Chuyển đổi số thành vector chữ số
{
    vector<int> a;
    /// Đẩy từng chữ số cuối cùng của n vào vị trí cuối mảng a
    do a.pb(n % 10); while (n /= 10);
    return reverse(a.begin(), a.end()), a;
}

int query() /// Với mỗi truy vấn
{
    /// Nhận phần tử
    ll l = readLong();
    ll r = readLong();

    /// Tính f(r)
    a = convert(r);
    n = a.size();
    f.assign(n + 1, vector<vector<ll> >(5, vector<ll>(2, -1)));
    ll fr = magic();

    /// Tính f(l - 1)
    a = convert(l - 1);
    n = a.size();
    f.assign(n + 1, vector<vector<ll> >(5, vector<ll>(2, -1)));
    ll fl = magic();

    /// Xuất ra
    cout << fr - fl << '\n';
    return 0;
}