SRM338 D1E-D2M ImprovingStatistics

TopCoder Statistics - Problem Statement
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

$played$, $won$が与えられる．勝率は$\displaystyle \frac{won}{played}$の百分率で表す(小数点以下は切り捨て)．これ以降プレイする場合は必ず勝つ場合に，あと何回プレイすれば勝率を$+1$することができるか．

あと何回プレイするかを$[0, 10 ^9 + 5)$で二分探索．勝率が$+1$を満たす最も小さいものを求める．$\displaystyle \frac{won}{played}$の百分率に端数が無い場合にfloorを用いると$-1$してしまうので，その場合は$+1$して戻す．

#include <bits/stdc++.h>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

class ImprovingStatistics {

    public:

    int howManyGames(int played, int won) {
      double a = played;
      double b = won;
      double t = floor(b / a * 100);

      if((t + 1) / 100 == b / a) {
          t++;
      }

      ll l = 0, r = 1e9 + 5;


      while(r - l > 1) {
          ll mid = (l + r) / 2;
          ll f = floor( ((b + mid) / (a + mid)) * 100 );
          if(f < t + 1) {
              l = mid;
          } else {
              r = mid;
          }
      }

      if(r == 1e9 + 5) return -1;
      return r;
    }
};