Todos los desafíos
Intermedio 1 resuelto 100.0% de aceptación

Tiempo de Producción en Fábrica

Encuentra el tiempo más temprano en que máquinas en paralelo pueden terminar una cantidad objetivo de productos.

Lo que aprenderás

  • Buscar en binario sobre el tiempo, no sobre las piezas
  • Comprobar en una pasada si un tiempo basta
  • Elegir límites de búsqueda seguros

Problema

Ver original (inglés)

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

Ejemplo 1
Entrada:
times = [2, 3]
target = 5

Salida esperada:
expected = 6
Entrada:
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.

Ejemplo 2
Entrada:
times = [4]
target = 3

Salida esperada:
expected = 12
Entrada:
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.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

# Programador Lenguaje Tiempo Memoria Revisión de IA Solución
1 ННикита Python 847 ms - 5/5 Ver código

Aprende de otros

Soluciones de la comunidad

Alerta de spoiler: 1 solución completa abajo Intenta resolverlo tú mismo primero. Igual puedes ver el código de otros desarrolladores y las reseñas de IA. Inicia sesión y resuelve el reto para unirte a la discusión.