Quy hoạch động chữ số (Digit DP) đếm số không chứa số 13
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
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: dp memoization, std string, std vector.
Nội dung đề bài
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 1018.
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 ≤ 1018). 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.
Input
- Một dòng duy nhất chứa hai số nguyên A và B (1 ≤ A ≤ B ≤ 1018).
Output
- In ra một số nguyên duy nhất là số lượng số hợp lệ trong đoạn [A, B].
Ràng buộc
- 1 ≤ A ≤ B ≤ 1018.
- Thời gian chạy: 1000ms.
- Bộ nhớ tối đa: 256MB.
Ví dụ 1
Input
1 20
Output
19
*Giải thích:* Trong khoảng từ 1 đến 20, chỉ có số 13 là chứa chuỗi con '13'. Do đó có 20 - 1 = 19 số hợp lệ.Ví dụ 2
Input
100 150
Output
40
*Giải thích:* Các số bị loại bỏ gồm: 113, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139... tổng cộng 11 số không hợp lệ trong 51 số → còn 40 số hợp lệ.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
