Trong biểu diễn thập phân chuẩn của một số, các số 0 ở đầu không được xem là chữ số của số đó.
Cho đoạn số nguyên đóng [A,B]. Hãy đếm các số trong đoạn có ít nhất một chữ số bằng 4 hoặc 9.
Input
Một dòng chứa hai số nguyên A và B.
Output
In số lượng số thỏa mãn trong đoạn [A,B].
Constraints
1≤A≤B≤1018.
Scoring
Subtask 1 (50 điểm):B≤105.
Subtask 2 (50 điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
39 45
Output
7
Giải thích: Các số 39,40,41,42,43,44,45 đều chứa ít nhất một chữ số 4 hoặc 9, nên cả bảy số trong đoạn đều được tính.
Lời giải tóm tắt
Ý tưởng: Dùng hàm tiền tố F(X) đếm các số trong [0,X]. Digit DP duyệt từ trái sang phải với hai cờ: tiền tố còn bằng X hay không và đã gặp chữ số 4/9 hay chưa. Đáp án là F(B)-F(A-1).
Tính đúng đắn: Ta chứng minh theo thứ tự các vị trí được duyệt. Ở mỗi trạng thái, các thành phần của trạng thái lưu đúng toàn bộ thông tin về tiền tố đã chọn có thể ảnh hưởng đến phần còn lại. Mỗi chữ số hoặc bit hợp lệ tiếp theo được xét đúng một lần, đồng thời điều kiện giới hạn bảo đảm tiền tố không vượt cận đang đếm. Vì thế mọi giá trị hợp lệ xuất hiện đúng một đường đi và mọi đường đi được cộng đều tương ứng với một giá trị hợp lệ. Khi dùng hiệu hai hàm tiền tố, mỗi phần tử trong đoạn đóng được tính đúng một lần.
Độ phức tạp: O(L·10) thời gian và O(1) bộ nhớ, với L là số chữ số của B.
Ý tưởng: Duyệt từng số trong đoạn và tìm ký tự 4 hoặc 9 trong chuỗi thập phân.