SRM483 Div1 Easy

250
やるだけ。桁数に注意する。

class BestApproximationDiv1 {
public:
  string findFraction(int maxDen, string s) 
  {
    int best = 0;
    int a, b;
    char buff[100];
    a = b = 0;
    for (int i = 0; i <= maxDen; ++i) {
      for (int j = 1; j <= maxDen; ++j) {
        double n = (double)i / (double)j;
        sprintf(buff, "%.10lf", n);
        string t(buff);
        int pref = 0;
        for (int k = 0; k < min(s.size(), t.size()); ++k) {
          if (s[k] != t[k]) break;
          pref = k;
        }
        if (best < pref) {
          a = i;
          b = j;
          best = pref;
        }
      }
    }
    
    sprintf(buff, "%d/%d has %d exact digits", a, b, best);

    return string(buff);
  }

};