CF - Mixing Water

Author: Jesse Choe

Table of Contents

ExplanationImplementation

The official editorial uses an O(1)\mathcal{O}(1) algorithm. This explanation will cover the binary search algorithm.

Official Editorial (C++)

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 ci+1c_i + 1 cups of hot water and cic_i cups of cold water for some ci0c_i \geq 0.
  • It can be proven, using induction, that the average barrel temperatures when cic_i is odd is a monotonically decreasing function. Thus, we can binary search on the maximum number of odd cups cic_i which gives a temperature of at least tt by checking the odd integers around it.

The answer will either be the barrel with 22, cic_i, or ci+2c_i + 2 cups.

Implementation

Time Complexity: O(logN)\mathcal{O}(\log N)

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 sys
for _ in range(int(input())):
hot, cold, target = map(int, input().split())
if target * 2 <= hot + cold:
print(2)
continue
lo = 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!