Link Sub: http://www.spoj.com/PTIT/problems/BCTEST13/
Người Gửi: Dương Lee
- Problem:
Cùng sở thích với Bờm, Tèo cũng rất thích các số may mắn. Ta đã biết rằng một số gọi là số may mắn nếu biểu diễn thập phân của nó chỉ chứa các chữ số may mắn là 4 và 7. Ví dụ: Các số 47,744,4 là số may mắn còn 5,17,467 không phải là số may mắn. Nhưng khác với Bờm, Tèo lại định nghĩa next(x) là số may mắn bé nhất lớn hơn hoặc bằng x.
Mở rộng hơn nữa, Tèo lại nghĩ ra Tổng may mắn LKSUM của hai số l,r (l≤r) như sau:
LKSUM=next(l)+next(l+1)+...+next(r-1)+next(r)
Bài toán đã trở nên khó khăn hơn nên Tèo cần sự giúp đỡ của các bạn sinh viên PTIT. Hãy giúp Tèo bài toán trên nhé !!!
Input
Một dòng duy nhất chứa hai số nguyên l và r (1≤l≤r≤109).
Output
Một số nguyên duy nhất là giá trị của tổng LKSUM.
Example:
Một số nguyên duy nhất là giá trị của tổng LKSUM.
Input
2 7
Output:
33
Giải thích: next(2)+next(3)+next(4)+next(5)+next(6)+next(7)=4+4+4+7+7+7=33
Input
7 7
Output:
7
Giải thích: next(7)=7
- Solution:
- Cách làm:
+ Sinh các trường hợp từ 1->10 chữ số cho 4 và 7; Sau khi sinh sẽ có mảng dãy số v[]={ 4, 7, 44, 47, ..., 77..7 } được đánh số thứ tự từ 0, 1, 2, 3, ...., size().
+ Chặt nhị phân tìm số lớn hơn gần với nó nhất trong mảng v. (p/s vì sinh tối đa 10 chữ số nên độ phức tạp cũng không nhiều khoảng O(10000) nên có thể dùng tìm kiếm tuyến tính).
+ Xét các trường hợp và tính toán các khoảng tạo ra.
VD: 2 và 8 -> tìm được: 4 và 44 -> tạo ra các khoảng: (2, 4] gồm các số có next()=4; (4, 7] gồm các số có next()=7; (7, 8] gồm các số có next()=44;
Như vậy chỉ cần biết được các khoảng chia sẽ biết được có bao nhiêu số trong đó có cùng giá trị next.Input
7 7
Output:
7