DEMSO - Đếm số

Giới hạn
  • Thời gian: 0.167s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua Codeforces (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên Codeforces. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên Codeforces

Với một số tự nhiên được viết trong hệ cơ số 10, ta định nghĩa vị trí xấu là vị trí mà chữ số tại đó với chữ số kề sau nó có độ chênh lệch không quá D. Nếu một số có không quá K vị trí xấu thì đó là số đẹp.

Hãy đếm số lượng số đẹp trong khoảng từ A đến B.

Dữ liệu

Gồm một dòng duy nhất là 4 số A, B, D, K.

Kết quả

Gồm một dòng duy nhất là số lượng số đếm được.

Giới hạn

1 ≤ A ≤ B ≤ 10 15

Ví dụ

Dữ liệu
1 13 1 0

Kết quả
10


  • Người up: beo_map
  • Nguồn bài: VNOI Marathon '08 - Practice RoundProblem Setter: Khúc Anh Tuấn