Los vehículos se amontonan en el embarcadero para cruzar el estuario. Por orden de llegada tienen las longitudes:
3m, 5m, 9m, 14m, 6m, 10m, 11m, 13m, 7m, 8m, 15m, 11m, 8m, 4m.
El transbordador tiene 3 calzadas, cada una de 40 metros de largo, pero el embarcadero tiene de ancho una calzada, así que solo se pueden cargar de uno en uno.
El patrón es un poco obtuso, quiere cargar al máximo la calzada de babor, mover el barco a la siguiente pista, cargar la del medio y mover de nuevo para cargar la de estribor. Queremos convencerle de que merece la pena hacer las cosas un poco más flexiblemente y que quepan más vehículos en el mismo viaje, así que, para este caso concreto:
- Calcular el porcentaje de largo de calzadas que se desaprovecha si el barco se carga según las ideas del patrón y sin cambiar de orden de llegada a los pacientes viajeros
- Calcular cuántos vehículos caben en el transbordador si nos permite elegir en cuál de las pistas metemos cada vehículo moviendo un poco el barco, ojo que si se embarca un vehículo ha debido embarcarse cualquiera que haya llegado antes que él, sólo se elige a lo ancho.
- Calcular cuántas veces tenemos que mover el barco a izquierda o derecha.
- Suponiendo que cada vehículo paga una cantidad p por el billete, independiente de su longitud, que el costo de cada movimiento del barco para ajustar calzadas tiene un coste (incluido tiempo y cualquier etc.) c y que el viaje de cruzar el río supone un gasto de r, elige tu unidad monetaria preferida, discutir los valores umbrales relativos de p, c y r para que merezca la pena cargar en plan creativo o a lo bolondrón.
Supongamos que dentro del barco, pese a haber 3 calzadas, están separadas de algún modo que impide que los vehículos maniobren y se coloquen donde un operario les indique.
Comentarios
Método 1:
calzada A: 3, 5, 9, 14, 6 -> 37
calzada B: 10, 11, 13 -> 34
calzada C: 7, 8, 15 -> 31
orden: A A A A A B B B C C C
2 movimientos: A -> B -> C
entran 11 vehículos, se desaprovecha el 15% del espacio
Metodo 2:
calzada A: 3, 5, 11, 13, 8 -> 40
calzada B: 9, 14, 6, 11 -> 40
calzada C: 10, 7, 8, 15 -> 40
orden: A A B B B C A A C C C B A
6 movimientos: A -> B -> C-> A -> C -> B -> A
entran 13 vehículos, se aprovecha todo
(cambiando la pista de los vehículos de 11m, se puede hacer con otro orden alternativo, pero el resultado final es el mismo. Ordenando de otras formas se aprovecha todo, pero hacen falta más movimientos)
El beneficio con el método 1 será:
(11p) - ((2*c)+r)
Si los movimientos largos (de A C, de pista izquierda a derecha, o viceversa) tienen el mismo coste que los movimientos cortos (de la central a uno de los lados o viceversa), el beneficio con el método 2 será:
(13p) - ((6*c)+r)
y merecerá la pena usar el método 2 si p>2c
Si los movimientos largos cuestan el doble, entonces el beneficio con el método 2 será:
(13p) - ((8*c)+r)
y merecerá la pena usar el método 2 si p>3c
Del valor de r dependerá solo si merece o no la pena cruzar el río.
#3 Buen trabajo.
#4 #3 Wow... yo ya he hundido el barco...
#6
#3 Se puede hacer en 5 movimientos
AAABCCCCBAABB < la más barata
AAABCCCCAABBA
AAABBCCBBAACC
#5 Bien visto, reconozco que no fui muy exhaustivo buscando combinaciones.
En el mejor caso, merecerá la pena usar el método 2 si 2p>3c (todos los movimientos son cortos).
Nachete, otro de barcos, no es complicado, pero es de barcos
#1 Todos llevamos dentro un rarito de los barcos, es cuestión de que se den las condiciones y pida salir ^^
En casa lo intento resolver
Paso de hacerte los deberes gratis
#8 Yo soy la profe, me los hacen los alumnos...