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;
            }

Codeforces Beta Round #91 (Div. 2 Only) - B. Lucky Substring

problem statement
After reading the problem statement carefully and checking the sample test cases, I noticed this part of the problem "needs the lexicographically minimum one", and thought by myself if it is gonna be a substring of input and lucky and lexicographically minimum one, then it has to be "4" or "7" because other substrings that are lucky contain 4 and 7, and there is no lucky number other than "4" or "7" that is repeated more times than "4" or "7" because at least the lucky number is going to be "44", "77", "47", "74", and at this cases "4" and "7" are repeated more times than these substrings.
So I just iterated through input string and counted number of 4's and number of  7's, if there is no 4 or 7, then output -1, otherwise if cnt7 is less than cnt4 output 4 else output 7.

Codeforces Beta Round #91 (Div. 2 Only) - A. Lucky Division

problem statement
As you read in the problem statement, you have to find out whether a number has a divisor which is also a lucky number, so iterate from 1 to n, if n is divisible by i, then check whether it is a lucky number or not?
Easily write a function that take a number and tell whether it is lucky or not, in other words the function checks whether all of the digits in the given number are 4 or 7.


  1. bool isLucky(int n)
  2. {
  3.     int rem;
  4.     while(n)
  5.     {
  6.         rem = n%10;
  7.         if(rem != 7 && rem != 4)
  8.             return false;
  9.         n /= 10;
  10.     }
  11.     return true;
  12. }

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...