← Volver a los ejercicios

Bisección sobre la respuesta: repartir textos entre empleados

Aquí no hay un arreglo donde buscar: lo que se recorre con la bisección son los valores posibles de la respuesta. La actividad tiene tres tramos: unas preguntas para plantear el problema, la corrida del código sobre un ejemplo, donde usted decide cada paso, y un ejemplo distinto para intentarlo sin ayuda. Una respuesta equivocada explica qué falló y se puede volver a intentar.

1. El planteamiento

Hay M textos en orden y k empleados. Cada empleado recibe textos seguidos, y cada texto queda entero con uno solo. Se tarda un minuto por página. Se pide repartir de modo que el empleado con más páginas tenga las menos posibles.

Ejemplo: nueve textos de 100 a 900 páginas y k = 3. Mueva t, el máximo de páginas que se le permite a un empleado, y mire dónde caen los cortes: cada empleado toma textos mientras quepan y el siguiente sigue desde ahí. En rojo queda un texto más largo que t.


2. La corrida sobre el ejemplo

Se abre al terminar las preguntas.

Primero la comprobación: empleados_necesarios con t = 2000

Ahora la bisección con k = 3

Azul: los topes que siguen en duda. Rojo: descartados porque no alcanzan. Verde: descartados porque alcanzan y ya hay uno menor o igual en el intervalo.

3. Qué responde el código con cada error

Se abre al terminar las preguntas.

Son errores que compilan y corren. Escoja uno: la fila muestra los cortes del tope que ese programa responde.

4. Inténtelo sin ayuda

Se abre al terminar las preguntas.

Otros textos y otro k. Haga la bisección en papel y escriba el menor tope.