Costo mínimo
12a OMI, Torreón 2007
Descripción
Karel entró a una nueva escuela para aprender un poco más sobre ciencias de la computación. De tarea le dejaron resolver este problema de optimización.
Dado un conjunto de enteros positivos, definamos el costo de sumar dos números (a, b) de dicho conjunto como costo(a, b) = a + b. Suponiendo que Karel solamente puede hacer sumas de dos números, calcula el costo mínimo necesario para obtener la suma total de todos los elementos del conjunto.
Explicación
Supongamos que el conjunto inicial es {6, 3, 5, 7}. Queremos obtener la suma de todos los elementos del conjunto, sin embargo, cada suma tiene un costo equivalente al valor de la suma misma. Supongamos que decidimos sumar en el siguiente orden:
En este ejemplo primero sumamos los elementos 6 y 3 para obtener 9, esto nos deja el conjunto con los elementos {9, 5, 7}, el costo de la suma es de (6 + 3) = 9, el costo total acumulado es de 9. En el segundo paso sumamos los elementos 9 y 5 para obtener 14, el conjunto queda ahora como {14, 7}, el costo de la suma es de (9 + 5) = 14 y el costo total acumulado es de (9 + 14) = 23, sumando los costos del los pasos 1 y 2. Por último en el tercer paso sumamos el 14 y el 7 para obtener 21 con un costo de 21 y un costo total de (23 + 21) = 44. En resumen, obtuvimos la suma de todos los elementos del conjunto inicial con un costo de 44.
Sin embargo, el costo varía dependiendo del orden en que decidamos sumar los elementos, abajo se muestra un segundo ejemplo sumando en un distinto orden.
En este segundo ejemplo se observa que al variar el orden en que se suman los números se puede obtener un costo total de 42, el cual es menor al del primer ejemplo.
Para el ejemplo anterior, 42 es el costo mínimo posible que se puede obtener.
Problema
Dado el conjunto de números representado como una línea de beepers que se encuentra en la primera fila, ayuda a Karel a calcular el costo mínimo posible para obtener la suma de los elementos y dejar un número de beepers igual a dicho costo en la posición (1, 2) del mundo.
NOTA: El resultado debe ser el costo mínimo posible, no la suma de los elementos del conjunto.
Consideraciones
- Karel inicia en la posición (1, 1) del mundo viendo hacia el este.
- Karel inicia con un número infinito de beepers en su mochila.
- El conjunto de números se representa como una línea de beepers sin espacios que se encuentra en la fila 1 comenzando a partir de la posición (1, 1).
- El conjunto de números nunca tendrá más de 16 elementos.
- Los elementos del conjunto son valores entre 1 y 100.
- No hay paredes dentro del mundo.
- No importa la posición ni orientación final de Karel.
- A excepción de la posición (1, 2), no importa la cantidad de beepers que haya en cualquier posición del mundo al finalizar la ejecución del programa.
Ejemplo
Mundo de ejemplo
Solución al mundo de ejemplo
Agradecimiento
Se agradece al Comité Olímpico Mexicano de Informática el permiso para publicar este problema en nuestro sitio; que fue aplicado en el examen nacional de la 12a OMI, celebrada en la ciudad de Torreón, Coahuila en el año 2007.