SRM 462 div1

Submitted 250 problem but challenged. The result was 0pt and rating was 1257. The rating slightly gained but I’m not satisfied the result. Also the result of the SRM had been 0pt in which recent 3 matches.

Easy – AgeEncoding

The algorithm for this problem is not so hard, this is just a problem for searching the solution with binary search. However, the most difficult point is consideration for corner cases. According to problem statement, we should return -1 if there is no solution and -2 if there are multiple solution. And it was very hard to notice all cases of such conditions. Many coders had been challenged or failed system test. It seems that almost of them hadn’t noticed the case whose input are, for instance, age = 1 and candlesLine = “11111″. In this case the correct answer is -1, not 0, since return value must be “strictly positive”.

class AgeEncoding {
public:
  double getRadix(int age, string candlesLine) {
    double ret = 0;
    int i, j;
    int n = candlesLine.size();
    int one_num = count(candlesLine.begin(), candlesLine.end(), '1');

    if (one_num == 0) return -1;
    if (candlesLine[n-1] == '1')
      if (age == 1)
        if (one_num == 1) return -2;
        else return -1;
      else
        if (one_num == 1) return -1;
    
    double left = 0, right = 100;
    for (i=0; i<1000; i++) {
      ret = (left + right) * 0.5;
      double ans = 0;
      double B = 1;

      for (j=n-1; j>=0; j--) {
        ans += (candlesLine[j] - '0') * B;
        B *= ret;
      }

      if (ans > age)
        right = ret;
      else
        left = ret;
    }

    return ret;
  }
};

Advertisement