CF #1359 C – Mixing Water

Problem C –  Mixing Water

Problem Statement – https://codeforces.com/contest/1359/problem/C

The problem involves binary search and some observations. Assume h = hot water temperature, c = cold water and t = given temperature.

Observations

  1. The maximum temperature of barrel = h
  2. The minimum possible temperature = (h+c)/2 achieved at every even cup.
    1. At every even number of cups, the temperature is the same and is equal to (h+c)/2.
    2. Assume there are k cups and k is even, the avg is (h*k/2+c*k/2)/k which is (h+c)/2 only.
  3. If the temperature is less than the minimum possible, ans is simply 2.
  4. If the temp is greater than max possible, ans is simply 1.
  5. For rest cases, the temperature when we pour odd cups, always decreases if we consider only odd cups. We can apply binary search to get the number of cups such that the temp is greater than or equal to t.
  6. Once we did binary search, we need to run a loop to check for the absolute difference for temperatures which are less than t also. Since, binary search will give us the number of cups which are greater than or equal to t, we can check for the difference by choosing to check for next 100 cups (only odd pos).
  7. Note that we are applying binary search on number of hot cups poured, because that is a decreasing function.
double h,c,t;
double calculate(ll i){
    return (c*(0.0+i-1) + h*(0.0+i))/(0.0+i+i-1);
}

void solve()
{
	cin >> h >> c >> t;
    if (t >= h){
        cout << 1 << endl;
        return;
    }
    if (t <= (h+c)/2){
        cout << 2 << endl;
        return;
    }
    ll low = 1;
    ll high  = 1ll<<38;
    ll steps;
    while(low <= high){
        ll mid = (low+high)/2;
        double cavg = calculate(mid);
        if (cavg >= t){
            steps = mid;
            low = mid+1;
        }
        else high = mid-1;
    }
    ll ans = 2;
    double avg = (h+c)/2.0;
    rep(i,0,101){
        double cavg = calculate(steps+i);
        if (abs(t-cavg) < abs(t-avg)){
            ans = steps+i;
            avg = cavg;
        }
    }
    cout << 2*ans-1 << endl;
    
}

Leave a Reply