解いた問題

7/21/2011

SRM462 Div1 Easy

250
見るからに二分探索。
コーナーケースに注意する。
何度かリサブミットしてやっと通った。Easyじゃないと思った。
class AgeEncoding {
public:
  double getRadix(int age, string line) {

    while( line.size() && line[0] == '0' )line.erase( line.begin() );
    if( line.size() == 0 )line = "0";

    if( age == 1 && line == "1" )return -2;

    if( age == 1 && 1 < line.size() && line[(int)line.size() - 1] == '1' )return -1;

    reverse( line.begin(), line.end() );

    double s = 0;
    double b = 1000000.0;

    double sum, c, w;
    for(int loop = 1000; loop--; ){
      w = 1;
      c = (s + b) / 2.0;
      sum = 0;
      for(int i=0; i<line.size(); ++i){
        if( line[i] == '1' )sum += w;
        w *= c;
      }
      if( sum >= (double)age )b = c;
      else s = c;
    }

    return fabs(sum - (double)age) <= 1e-8 ? b : -1;
  }
};

0 件のコメント :

コメントを投稿