CLBATH - Editorial

editorial
, , , ,
1

PROBLEM LINK

Practice
Contest

Author and Editorialist: Soumik Sarkar
Tester: Avijit Agarwal

DIFFICULTY

SIMPLE

PREREQUISITES

Basic maths

PROBLEM

There are two buckets of water. The water in the first bucket has volume v_1 and temperature t_1. The water in the second has volume v_2 and temperature t_2. It is given t_1 < t_2 and the problem to find if some water from the 2 buckets can be combined to get at least v_3 volume at temperature t_3 .

EXPLANATION

First of all, it is impossible to get water at temperature less than t_1 or more than t_2. After this check there can be multiple more-or-less equivalent methods to solve this problem. Author’s solution is as follows.

Mixing v_x volume of water at temperature t_1 with v_y volume of water at temperature t_2 yields water at temperature t_3, where

t_3 = \frac{v_x t_1 + v_y t_2}{v_x + v_y}

Manipulating the equation, we get

\frac{v_x}{v_y} = \frac{t_2 - t_3}{t_3 - t_1}

This is the fixed ratio in which the water from the two buckets must be mixed to get temperature t_3.

To get v_3 volume, the conditions

\frac{v_x}{v_x + v_y} \cdot v_3 \le v_1 \\ \frac{v_y}{v_x + v_y} \cdot v_3 \le v_2

must hold.

Time complexity is \mathcal{O}(1) per case.

AUTHOR’S AND TESTER’S SOLUTIONS

Author’s solution can be found here
Tester’s solution can be found here.

2 Likes
3

given constraints is t2>t1

4

Yes, as @goti158 said, t2 must be greater than t1

5

how the conditions of getting volume v3 is working? basically how to get that conditions??

7

I write the solution but I don’t know why it is failing.

MyCode:

#include<bits/stdc++.h>
#include <unistd.h>
using namespace std;
#define ll long long
#define ull unsigned long long


ll gcd(ll a,ll b){
	if(b==0) return a;

	return gcd(b, a%b);
}


ll max(ll a,ll b){
	return a>=b?a:b;
}
void go() {
    ll v1, t1, v2, t2, v3, t3;
    cin >> v1 >> t1 >> v2 >> t2 >> v3 >> t3;

    // Handle the special cases where t3 == t1 or t3 == t2 directly
    if (t3 == t1) {
        if (v1 >= v3) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
        return;
    }
    
    if (t3 == t2) {
        if (v2 >= v3) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
        return;
    }

    // If t3 is outside the range of t1 and t2, it's impossible
    if (t3 < t1 || t3 > t2) {
        cout << "NO\n";
        return;
    }

    ll req_vol1 = (t2 - t3);
    ll req_vol2 = (t3 - t1);

    ll _gcd = gcd(req_vol1, req_vol2);

    req_vol1 /= _gcd;
    req_vol2 /= _gcd;

    ll total_ratio = (req_vol1 + req_vol2);

    ll unit1 = 1e9;
    ll unit2 = 1e9;

    if (req_vol1 != 0)
        unit1 = v1 / req_vol1;
    if (req_vol2 != 0)
        unit2 = v2 / req_vol2;

    ll total_req = min(unit1, unit2);

    total_req *= total_ratio;

    if (total_req >= v3) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}


int main(){
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin); 
	freopen("output.txt","w",stdout);
	#endif
	int t; cin>>t;

	while(t-->0){
		go();
	}

	return 0; 
}