Блог пользователя ICPCkiller

Автор ICPCkiller, 13 лет назад, По-английски

    "Complete search exploits the brute force, straight-forward, try-them-all method of finding the answer. This method should almost always be the first algorithm/solution you consider. If this works within time and space constraints, then do it: it's easy to code and usually easy to debug. This means you'll have more time to work on all the hard problems, where brute force doesn't work quickly enough.

In the case of a problem with only fewer than a couple million possibilities, iterate through each one of them, and see if the answer works. "                                                                                   

--USACO

    In the Codeforces Round #104 (Div. 2),problem B .Lucky Mask is just a brut force problem.In the contest, I didn't realize that.

    "Petya calls a mask of a positive integer n the number that is obtained after successive writing of all lucky digits of number n from the left to the right. For example, the mask of number 72174994 is number 7744, the mask of 7 is 7, the mask of 9999047 is 47. Obviously, mask of any number is always a lucky number."

--B. Lucky Mask

    This sentence shows that how the examine progress work. The try-them-all program is like the following code:

for(c=(a+1);;c++)
   if(mask(to(c))==sb)
   {
      cout<<c<<endl;
      break;
   }

    The function of to(c) is to tranform the interger to string and the function mask() can return the mask of the number which is larger than a, through comparision between b and the mask, we can easily get the answer.

    string to(double x)
{
  ostringstream o;
  if(o<<x)
     return o.str();
  return "error";
}

string mask(string s)
{
  string::iterator it=s.begin();
  while(it!=s.end())
  {
    if(*it!='4'&&*it!='7')
    {
      s.erase(it);
      continue;
    }
    it++;
  }
  return s;
}

    That's my idea and I hope that you like it !

    Contact me :liyue@whu.edu.cn

Полный текст и комментарии »

  • Проголосовать: нравится
  • -22
  • Проголосовать: не нравится