El nombre del problema refleja tu tarea: sumar, aunque si somos más especificos, se trata de sumar una lista de números. Quizá piensas: “Meh, sólo se trata de un programa para sumar”, pero hay una pequeña situación a tomar en cuenta... Para sumar dos números, ¡tienes que pagar un monto igual a la suma de ellos!
Por ejemplo, para sumar 3 y 7 hay que pagar monto igual a 10, y para sumar 2 y 4 un monto igual a 6. Ahora bien, si queremos sumar 1, 2 y 3 podemos hacerlo de varias formas:
Forma 1
1 + 3 = 4, costo actual = 4
2 + 4 = 6, costo actual = 6
Monto total = 10
Forma 2
2 + 3 = 5, costo actual = 5
1 + 5 = 6, costo actual = 6
Monto total = 11
Forma 3
1 + 2 = 3, costo actual = 3
3 + 3 = 6, costo actual = 6
Monto total = 9
De entre estas tres formas, la más barata es la tercera.
¡Basta de ejemplos! Ahora te toca a ti: Te entregaremos varias listas de números, y para cada una de ellas, tendrás que decirnos cuál es el costo más barato de adición.
La entrada contiene varias listas.
La descripción de cada lista comienza con un número entero N (2 = N = 5000) que indica su cantidad de elementos. En la línea siguiente se encuentran N números enteros positivos (menores a 100,000) separados por espacios. Estos son los números de la lista.
Una lista con 0 elementos (N = 0) señala el final de la entrada. No debes procesar esta lista.
Para cada lista, imprime el costo mínimo de adición en una sola línea.
3 1 2 3 4 1 2 3 4 0
9 19