DEMSO - Đếm số

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

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