Friday, January 6, 2012

Codeforces Beta Round #91 (Div. 2 Only) - C. Lucky Sum

problem statement
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 all;
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

USACO - Prime Palindromes

I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everyth...