Baroibeo Number

Xem PDF

Đ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


    • -1
      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 RiLi - 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;
      }