Skip to content
GitHub Twitter

TopCoder SRM 676 Div.1 Easy: Water Tank


  • You are given an empty water tank with a capacity of \(C\) liters.
  • Into this tank, the water flows \(x[i]\) liters for \(t[i]\) seconds. (\(i = 0\) to \(n - 1\))
  • You can set the value of output pipe to any maximum output rate \(R\) (not negative value, but do not have to be an integer) in liters per second.
  • Determine the most little output rate limit \(R\) such that the amount of water in the tank will never exceed \(C\) liters.


  • When it comes to "Find the maximum of the minimum," we can use Binary Search.
  • The returning value can be double, so we apply binary search until the difference between the left and the right value becomes less than the acceptable error.


const double EPS = 1e-9;
const Inf = 1e9;
double minOutputRate(vector<int> t, vector<int> x, int C) {
  int n = (int)t.size();
  double left = -EPS, right = Inf, mid;
  while (right - left > EPS) {
  mid = (right + left) / 2;
  double rem = 0.0;
  bool ok = true;
  for(int i = 0; i < n; i++) {
	rem += (x[i] - mid) * t[i];
	rem = max(rem, (double)0);
	if (rem > C) {
	  ok = false;
  if (ok)
	right = mid;
	left = mid;
  return right;