Loan Repayment

Explicación

Primero, notemos que podemos hacer búsqueda binaria sobre la respuesta, o $X$ en este caso. Para cada $X$ , debemos comprobar si es válido y actualizar la búsqueda binaria en consecuencia. Podemos hacer búsqueda binaria sobre $X$ porque, para valores más pequeños de $X$ , estamos dando más galones de leche. Por lo tanto, si es posible que un valor de $X$ cumpla el requisito, también es posible para todos los valores menores que ese $X$ .

Para determinar de forma eficiente si un valor de $X$ dado es válido, podemos simular el proceso. Sin embargo, procesamos de una sola vez todos los estados en los que $Y$ , el número de galones que Farmer John paga, no cambia.

Además, notemos que si Farmer John da más de $\sqrt{2N}$ valores distintos de $Y$ , entonces definitivamente habrá pagado la deuda, ya que $1 + 2 + \ldots + \sqrt{2N} \ge N$ , lo que significa que la cota superior del número de operaciones que debemos hacer es $\sqrt{2N}$ , cumpliendo nuestras restricciones de tiempo.

Por lo tanto, podemos validar un valor dado de $X$ en $\mathcal{O} (\sqrt{N})$ tiempo, y la solución completa corre en $\mathcal{O}(\sqrt{N}\cdot \log {N})$ .

Implementación

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

C++JavaPython


#include <algorithm>
#include <fstream>
#include <iostream>
 
using std::cout;
using std::endl;
 
/**
 * @return si Farmer John le da a Bessie al menos N (numGallons)
 * galones de leche dentro de withinDays con el valor de X dado
 */
bool can_repay(long long num_gallons, long long within_days, long long at_least,
               long long x_val) {
	long long g = 0;
	while (within_days > 0 && g < num_gallons) {
		long long y = (num_gallons - g) / x_val;
		if (y < at_least) {
			long long leftover = ((num_gallons - g) + (at_least - 1)) / at_least;
			return leftover <= within_days;
		}
 
		long long max_match = num_gallons - (x_val * y);
		long long num_days = std::min((max_match - g) / y + 1, within_days);
 
		g += y * num_days;  // actualizamos los valores
		within_days -= num_days;
	}
 
	return g >= num_gallons;
}
 
int main() {
	std::ifstream read("loan.in");
 
	long long num_gallons;
	long long within_days;
	long long at_least;
	read >> num_gallons >> within_days >> at_least;
 
	// búsqueda binaria del mayor X
	long long low = 1;
	long long high = INT64_MAX / 2;
	while (low < high) {
		long mid = (low + high + 1) / 2;
		if (can_repay(num_gallons, within_days, at_least, mid)) {
			low = mid;
		} else {
			high = mid - 1;
		}
	}
 
	std::ofstream("loan.out") << low << endl;  // low == high, podemos imprimir cualquiera
}


import java.io.*;
import java.util.*;
 
public class Loan {
	/**
	 * @return si Farmer John le da a Bessie al menos N (numGallons)
	 * galones de leche dentro de withinDays con el valor de X dado
	 */
	static boolean canRepay(long numGallons, long withinDays, long atLeast, long xVal) {
		long g = 0;
		while (withinDays > 0 && g < numGallons) {
			long y = (numGallons - g) / xVal;
			if (y < atLeast) {
				long leftover = ((numGallons - g) + (atLeast - 1)) / atLeast;
				return leftover <= withinDays;
			}
 
			long maxMatch = numGallons - (xVal * y);
			long numDays = Math.min((maxMatch - g) / y + 1, withinDays);
 
			g += y * numDays;  // actualizamos los valores
			withinDays -= numDays;
		}
 
		return g >= numGallons;
	}
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("loan");
		long numGallons = io.nextLong();
		long withinDays = io.nextLong();
		long atLeast = io.nextLong();
 
		// búsqueda binaria del mayor X
		long low = 1;
		long high = Long.MAX_VALUE / 2;
		while (low < high) {
			long mid = (low + high + 1) / 2;
			if (canRepay(numGallons, withinDays, atLeast, mid)) {
				low = mid;
			} else {
				high = mid - 1;
			}
		}
 
		io.println(low);  // low == high, podemos imprimir cualquiera
		io.close();
	}
 
	// CodeSnip{Kattio}
}


def can_repay(num_gallons: int, within_days: int, at_least: int, x_val: int) -> bool:
	"""
	:return: si Farmer John le da a Bessie al menos N (num_gallons)
	galones de leche dentro de within_days con el valor de X dado
	"""
	g = 0
	while within_days > 0 and g < num_gallons:
		y = (num_gallons - g) // x_val
		if y < at_least:
			leftover = (num_gallons - g + at_least - 1) // at_least
			return leftover <= within_days
 
		max_match = num_gallons - x_val * y
		num_days = min((max_match - g) // y + 1, within_days)
 
		g += y * num_days  # actualizamos los valores
		within_days -= num_days
 
	return g >= num_gallons
 
 
with open("loan.in") as read:
	num_gallons, within_days, at_least = map(int, read.readline().split())
 
# búsqueda binaria del mayor X
low = 1
high = 10**12
while low < high:
	mid = (low + high + 1) // 2
	if can_repay(num_gallons, within_days, at_least, mid):
		low = mid
	else:
		high = mid - 1
 
print(low, file=open("loan.out", "w"))  # low == high, podemos imprimir cualquiera