After reading the problem statement, at first I was shocked by the range of input, 1<=left<=right<=10^9, but after a close look to the problem again, I found that there are not too much lucky numbers in the range, I recursively generate lucky numbers with this function :
#define ll (long long)
vector
void back(ll v, ll p10)
{
all.push_back(v);
if(v > 1000000000)
return;
back(v+4*p10, p10*10);
back(v+7*p10, p10*10);
}
then I sort "all", sort(all.begin(), all.end()),
and after that, I iterate through "all", I have a variable x that is the leftmost point that next(x) is not calculated yet, then if x <= all[i] this means all of the points k in range [x, all[i]], next(k) = all[i],
so I add (all[i]-x+1) * all[i] to the output, but if for example input is like this 2 6, I add (4-2+1)*4 + (7-5+1)*7 which is wrong, actual output is (4-2+1)*4 + (6-5+1)*7 so I added this if else to my code :
if(all[i] <= right)
{
sum += (all[i]-x+1) * all[i];
x = all[i]+1;
}
else
{
sum += (right-x+1) * all[i];
x = all[i]+1;
}
No comments:
Post a Comment