Quy hoạch động chữ số (Digit DP) đếm số không chứa số 13

Mục tiêu kiến thức

• Hiểu nguyên lý xây dựng số từ trái sang phải bằng Quy hoạch động chữ số (Digit DP).
• Nắm vững trạng thái nén: vị trí chữ số pos, cờ chạm trần tight, và dấu hiệu chữ số đứng trước prev_is_one.
• Áp dụng nguyên lý cộng trừ: Count(A, B) = f(B) - f(A - 1) cho các số cực lớn lên tới 10¹⁸.

Mô tả bài toán

Hệ thống cấp phát định danh máy chủ bảo mật của AI Empire Academy quy định: Một số nguyên dương được coi là hợp lệ nếu trong biểu diễn thập phân của nó không chứa xâu con liên tiếp '13'.

Cho hai số nguyên A và B (1 ≤ A ≤ B ≤ 10¹⁸). Hãy đếm xem có bao nhiêu số nguyên trong đoạn [A, B] là số hợp lệ.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ A ≤ B ≤ 10¹⁸.
• Thời gian chạy: 1000ms.
• Bộ nhớ tối đa: 256MB.