CF - Mixing Water
Author: Jesse Choe
The official editorial uses an algorithm. This explanation will cover the binary search algorithm.
Explanation
Consider the following observations:
- Case 1: The number of cups of hot water poured is equal to the number of cups of cold water poured. Pouring an equal number of cups of hot and cold water is equivalent to pouring one cup of each.
- Case 2: Otherwise, there must be exactly one more cup of hot water poured than cold water poured. Thus, there will be cups of hot water and cups of cold water for some .
- It can be proven, using induction, that the average barrel temperatures when is odd is a monotonically decreasing function. Thus, we can binary search on the maximum number of odd cups which gives a temperature of at least by checking the odd integers around it.
The answer will either be the barrel with , , or cups.
Implementation
Time Complexity:
C++
#include <cstdint>#include <iostream>using std::cout;using std::endl;int main() {int test_num;std::cin >> test_num;for (int t = 0; t < test_num; t++) {
Java
import java.io.*;import java.util.*;public class MixingWater {public static void main(String[] args) {Kattio io = new Kattio();int testNum = io.nextInt();for (int t = 0; t < testNum; t++) {int hot = io.nextInt();
Python
import sysfor _ in range(int(input())):hot, cold, target = map(int, input().split())if target * 2 <= hot + cold:print(2)continuelo = 0
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!