1. Tóm tắt đề bài

Một số nguyên dương được gọi là "số tăng dần chữ số" nếu các chữ số của nó từ trái sang phải xếp theo thứ tự không giảm (chữ số đứng sau lớn hơn hoặc bằng chữ số đứng trước nó, ví dụ: ~123, 115~). Cho hai số nguyên dương ~a~ và ~b~ (~a \le b~). Hãy đếm xem có bao nhiêu số như vậy trong đoạn ~[a, b]~.

• Dữ liệu vào (Input):
  • Gồm một dòng chứa hai số nguyên dương ~a, b~ cách nhau bởi dấu cách (~1 \le a \le b \le 10^5~).
• Dữ liệu ra (Output):
  • Một số nguyên duy nhất là số lượng số thỏa mãn yêu cầu.

2. Phân tích bài toán & Giới hạn

• Giới hạn bài toán:

  • ~1 \le a \le b \le 10^5~.
  • Số lượng phần tử cần kiểm tra trong đoạn ~[a, b]~ tối đa là ~10^5~ số.
  • Mỗi số ~n \le 10^5~ có tối đa ~6~ chữ số. Thao tác kiểm tra từng chữ số của một số diễn ra trong tối đa ~6~ phép tính so sánh.

• Đánh giá thời gian & Bộ nhớ:

  • Tổng số phép tính toán toàn bài tối đa chỉ khoảng ~10^5 \times 6 \approx 6 \times 10^5~ phép tính.
  • Thời gian thực thi ~\approx 0.01~ giây, tối ưu tuyệt đối và hoàn toàn vượt qua giới hạn thời gian tiêu chuẩn ~1.0~ giây của hệ thống chấm tự động.
  • Các biến đều nằm trong khoảng ~10^5~, hoàn toàn sử dụng kiểu số nguyên thông thường 32-bit (int).

3. Thuật toán xử lý

• Xây dựng hàm kiểm tra bool check(int n):

  1. Nếu số ~n~ chỉ có 1 chữ số (~n < 10~), mặc nhiên thỏa mãn thứ tự không giảm, trả về true.
  2. Để kiểm tra tính chất không giảm từ trái sang phải mà không cần lưu mảng hay chuyển sang xâu:
     • Ta tách các chữ số từ phải sang trái (từ hàng đơn vị lùi dần về trước).
     • Khi đi từ phải sang trái, các chữ số phải có thứ tự không tăng (chữ số bên phải luôn ~\ge~ chữ số đứng liền kề bên trái nó).
     • Lấy chữ số cuối cùng hiện tại: int last = n % 10; n /= 10;.
     • Khi ~n > 0~, lấy chữ số kế tiếp: int prev = n % 10;.
     • Nếu prev > last (chữ số đứng trước lại lớn hơn chữ số đứng sau), vi phạm điều kiện không giảm ~\rightarrow~ trả về false.
     • Cập nhật last = prev; và bỏ chữ số vừa xét bằng n /= 10;.
  3. Nếu duyệt hết các chữ số mà không vi phạm, trả về true.

• Chương trình chính (main):

  1. Khai báo hai số a, b và biến đếm dem = 0.
  2. Đọc hai số bằng lệnh chuẩn: cin >> a >> b;.
  3. Dùng vòng lặp for (int i = a; i <= b; i++):
     • Nếu check(i) đúng thì tăng dem++.
  4. In biến dem ra màn hình và xuống dòng bằng cout << endl;.

• Độ phức tạp:

  • Thời gian: ~\mathcal{O}((b - a + 1) \cdot \log_{10}(b))~ — Duyệt qua tối đa ~10^5~ số, mỗi số kiểm tra tối đa ~6~ chữ số. Chạy tức thì (~< 0.02~ giây).
  • Bộ nhớ: ~\mathcal{O}(1)~ — Tiết kiệm bộ nhớ tuyệt đối.

4. Mã nguồn cài đặt (C++)

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

// Hàm kiểm tra số có các chữ số theo thứ tự không giảm từ trái sang phải
bool check(int n) {
    int last = n % 10;
    n /= 10;
    while (n > 0) {
        int prev = n % 10;
        if (prev > last) {
            return false;
        }
        last = prev;
        n /= 10;
    }
    return true;
}

int main() {
    // Tối ưu tốc độ vào/ra chuẩn
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int a, b;
    cin >> a >> b;

    int dem = 0;
    for (int i = a; i <= b; i++) 
    {
        if (check(i)) 
            dem++;
    }

    cout << dem << endl;

    return 0;
}