*【CodeForces - 122C 】Lucky Sum （bfs记录状态，二分查找，有坑）（或分块）_codeforces 122c

题干：

Petya loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Let next(x) be the minimum lucky number which is larger than or equals x. Petya is interested what is the value of the expression next(l) + next(l + 1) + ... + next(r - 1) + next(r). Help him solve this problem.

Input

The single line contains two integers l and r (1 ≤ l ≤ r ≤ 109) — the left and right interval limits.

Output

In the single line print the only number — the sum next(l) + next(l + 1) + ... + next(r - 1) + next(r).

Please do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specificator.

Examples

Input

2 7

Output

33

Input

7 7

Output

7

Note

In the first sample: next(2) + next(3) + next(4) + next(5) + next(6) + next(7) = 4 + 4 + 4 + 7 + 7 + 7 = 33

In the second sample: next(7) = 7

解题报告： 

   这题不难发现是状态的转移，每一个状态可以延伸到新的两个状态，所以考虑bfs搜索一下，然后二分查找位置就可以暴力了。这题的一个坑点在于，能否发现，当st和ed是相等的时候就不能分区间这么看了，而应该直接看这个区间。找个例子看啊：这种样例很好找啊，比如1e9 1e9这个样例。

AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll b[100005];
int tot;
void bfs() {
	priority_queue<ll,vector<ll>,greater<ll> > pq;
	tot = 0;
	b[++tot] = 4;pq.push(4);
	b[++tot] = 7;pq.push(7);
	while(!pq.empty()) {
		ll cur = pq.top();pq.pop();
		if(cur > (ll)1e12+7) return ;
		b[++tot] = cur*10+4;pq.push(b[tot]);
		b[++tot] = cur*10+7;pq.push(b[tot]);
	}
}
int main()
{
	bfs();
	ll l,r;
	cin>>l>>r;
//	cout << b[tot] << endl;
	ll ans = 0;
	int st = lower_bound(b+1,b+tot+1,l) - b;
	int ed = lower_bound(b+1,b+tot+1,r) - b;
	if(ed > st) {
		ans += (b[st] - l + 1) * b[st];
		for(int i = st+1; i<ed; i++) {
			ans += (b[i] - b[i-1]) * b[i];
		}
		ans += (r-b[ed-1]) * b[ed];
	}
	else ans += (r-l+1) * b[st];
	cout << ans << endl;
	return 0 ;
}

法2：分块：（还未看）

#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false);\
	cin.tie(0);\
	cout.tie(0);
 
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
 
ll last(ll x) {
	int len = int(log10(x)) + 1;    //数字位数
	ll ans = 0,cnt = 0;
	for(int i=0; i<len; i++)        //同等位数最大最小幸运数
		ans = ans*10+4,cnt = cnt*10+7;
	if(x>cnt)                       //位数+1
		return ans*10+4;
	while(ans<x) {
		ll res = cnt;
		for(int i=0; i<1<<len; i++) {
			ll tmp = 0;
			for(int j=0; j<len; j++) {
				if(i&(1<<j))
					tmp = tmp*10+7;
				else
					tmp = tmp*10+4;
			}
			if(tmp>=x)
				res = min(res,tmp);
		}
		ans = res;
	}
	return ans;
}
 
int main() 
{
	ll l,r;
	cin>>l>>r;
	ll now = l,ans = 0;
	while(true) {
		ll la = last(now);
		if(la>r) {
			ans+= la * (r-now+1);
			break;
		} else
			ans += la * (la-now+1);
		now = la+1;
	}
	cout<<ans<<endl;
	return 0;
}