Problema
Todas las máquinas comienzan en el tiempo 0 y trabajan de forma independiente. Una máquina con tiempo t termina un producto después de t segundos, otro después de 2t segundos, y así sucesivamente. Encuentra el primer segundo entero en que su producción combinada alcanza el objetivo.
Implementa factory_machines(times, target).
Entrada
times: Segundos necesarios para un producto en cada máquina.
target: La cantidad de productos terminados requerida.
Salida
Devuelve el mínimo número de segundos transcurridos.
Restricciones
1 ≤ máquinas ≤ 200,000. Cada tiempo y el objetivo están entre 1 y 1,000,000,000. La respuesta cabe en un entero con signo de 64 bits.
Ejemplos
Entrada:
times = [2, 3]
target = 5
Salida esperada:
expected = 6Entrada:
std::vector<long long> times = {2, 3};
long long target = 5;
Salida esperada:
long long expected = 6;Entrada:
long[] times = new long[] {2, 3};
long target = 5;
Salida esperada:
long expected = 6;Explicación
En el segundo 6 las máquinas han producido 3 + 2 = 5 productos. En el segundo 5 solo han producido 2 + 1 = 3.
Entrada:
times = [4]
target = 3
Salida esperada:
expected = 12Entrada:
std::vector<long long> times = {4};
long long target = 3;
Salida esperada:
long long expected = 12;Entrada:
long[] times = new long[] {4};
long target = 3;
Salida esperada:
long expected = 12;Explicación
Una máquina termina su tercer producto en 3 × 4 = 12 segundos.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Para un tiempo dado, puedes contar cuántos objetos producirían todas las máquinas juntas hasta entonces.
Pista 2
La respuesta es el menor tiempo en que esa cantidad producida alcanza el objetivo.
Pista 3
Una condición monótona como esta encaja muy bien con buscar sobre el tiempo en lugar de simular la producción.
Complejidad esperada
tiempo O(n log T), espacio extra O(1)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.