Mixing Water

La editorial oficial usa un algoritmo $\mathcal{O}(1)$ . Esta explicación cubre el algoritmo de búsqueda binaria.

Editorial oficial (C++)

Explicación

Consideremos las siguientes observaciones:

Caso 1: El número de vasos de agua caliente vertidos es igual al número de vasos de agua fría vertidos. Verter un número igual de vasos de agua caliente y fría es equivalente a verter un vaso de cada una.
Caso 2: En caso contrario, debe haber exactamente un vaso más de agua caliente que de agua fría. Así, habrá $c_i + 1$ vasos de agua caliente y $c_i$ vasos de agua fría para algún $c_i \geq 0$ .
Se puede demostrar, por inducción, que las temperaturas promedio del barril cuando $c_i$ es impar forman una función monótonamente decreciente. Así, podemos hacer búsqueda binaria sobre el número máximo de vasos impares $c_i$ que da una temperatura de al menos $t$ comprobando los enteros impares a su alrededor.

La respuesta será el barril con $2$ , $c_i$ o $c_i + 2$ vasos.

Implementación

Complejidad temporal: $\mathcal{O}(\log N)$

C++JavaPython


#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++) {
		int hot;
		int cold;
		int target;
		std::cin >> hot >> cold >> target;
 
		if (target * 2 <= hot + cold) {
			cout << 2 << '\n';
			continue;
		}
 
		long long lo = 0;
		long long hi = INT32_MAX;
		long long valid = -1;
		while (lo <= hi) {
			long long n = (lo + hi) / 2;
			long long num = (n + 1) * hot + n * cold;
			long long denom = 2 * n + 1;
			if (num >= denom * target) {
				valid = n;
				lo = n + 1;
			} else {
				hi = n - 1;
			}
		}
 
		long long err1_num =
		    hot * (valid + 1) + cold * valid - target * (2 * valid + 1);
		long long err1_denom = 2 * valid + 1;
 
		long long err2_num =
		    target * (2 * valid + 3) - hot * (valid + 2) - cold * (valid + 1);
		long long err2_denom = 2 * valid + 3;
 
		if (err1_num * err2_denom <= err2_num * err1_denom) {
			cout << 2 * valid + 1 << '\n';
		} else {
			cout << 2 * valid + 3 << '\n';
		}
	}
}


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();
			int cold = io.nextInt();
			int target = io.nextInt();
 
			if (target * 2 <= hot + cold) {
				io.println(2);
				continue;
			}
 
			long lo = 0;
			long hi = Integer.MAX_VALUE;
			long valid = -1;
 
			while (lo <= hi) {
				long n = (lo + hi) / 2;
				long num = (n + 1) * hot + n * cold;
				long denom = 2 * n + 1;
 
				if (num >= denom * target) {
					valid = n;
					lo = n + 1;
				} else {
					hi = n - 1;
				}
			}
 
			long err1Num = hot * (valid + 1) + cold * valid - target * (2 * valid + 1);
			long err1Denom = 2 * valid + 1;
 
			long err2Num =
			    target * (2 * valid + 3) - hot * (valid + 2) - cold * (valid + 1);
			long err2Denom = 2 * valid + 3;
 
			if (err1Num * err2Denom <= err2Num * err1Denom) {
				io.println(2 * valid + 1);
			} else {
				io.println(2 * valid + 3);
			}
		}
 
		io.close();
	}
 
	// CodeSnip{Kattio}
}


import sys
 
for _ in range(int(input())):
	hot, cold, target = map(int, input().split())
 
	if target * 2 <= hot + cold:
		print(2)
		continue
 
	lo = 0
	hi = sys.maxsize
	valid = -1
 
	while lo <= hi:
		n = (lo + hi) // 2
		num = (n + 1) * hot + n * cold
		denom = 2 * n + 1
 
		if num >= denom * target:
			valid = n
			lo = n + 1
		else:
			hi = n - 1
 
	err1_num = hot * (valid + 1) + cold * valid - target * (2 * valid + 1)
	err1_denom = 2 * valid + 1
 
	err2_num = target * (2 * valid + 3) - hot * (valid + 2) - cold * (valid + 1)
	err2_denom = 2 * valid + 3
 
	if err1_num * err2_denom <= err2_num * err1_denom:
		print(2 * valid + 1)
	else:
		print(2 * valid + 3)