Skip to content

Sumando números

by en 18/03/2013

¡Hola!

Después de estas dos semanas sin acertijos, ¡estamos de vuelta! Las convocatorias regionales de ProgramaMe han sido todo un éxito, y ya sólo queda esperar al concurso nacional que será en Junio. Mientras lo hacemos, tenemos ya preparados unos cuantos acertijos para vosotros. ¡Vamos con el primero!

En una lejana y primitiva civilización, tienen un modo de sumar arcaico que supone que la suma de dos números cueste más o menos esfuerzo dependiendo de qué números se estén sumando. Por ejemplo, para sumar 1 + 1 necesitan 2 segundos, y para sumar 3 + 4 necesitan 7. En general, para sumar los números a y b necesitan a+b segundos.

Cuando se ven obligados a sumar varios números, por ejemplo 1 + 2 + 3 + 4, se plantean primero en qué orden hacer las diferentes sumas, para tardar el menor tiempo posible. Por ejemplo, pueden hacer la suma agrupando los números de la forma ((1 + 2) + 3) + 4, es decir sumando primero 1+2, luego sumando al resultado el 3, y a su vez al resultado el 4. Eso supone que hacen en realidad tres sumas, cada una con un coste en tiempo:

  • 1 + 2 = 3
  • 3 + 3 = 6
  • 6 + 4 = 10

Al final, hacer la suma en ese orden les lleva 3 + 6 + 10 = 19 segundos.

Si hicieran la suma total agrupando los números de otra forma: 1 + (2 + (3+4)) el resultado sería mucho peor:

  • 3 + 4 = 7
  • 2 + 7 = 9
  • 1 + 9 = 10

que tiene un coste total de 7+9+10 = 26 segundos.

La pregunta que os hacemos hoy es ¿cuál es el mínimo tiempo necesario para sumar 9, 6, 3 y 1? ¿Y 4, 5, 6 y 7?

¿Eres capaz de generalizar cómo resolverlo para más de cuatro números? Por ejemplo ¿cuál es el mínimo tiempo para 2, 5, 7, 9, 20 y 40? Si das con ello y te gusta programar, puedes probar tu solución aquí.

¡¡Esperamos tu respuesta en los comentarios!!

Anuncios
5 comentarios
  1. Borja permalink

    Para 9, 6, 3 y 1 el tiempo mínimo es de 33 segundos.
    Para 4, 5, 6 y 7 el tiempo mínimo es de 46 segundos.
    Para 2, 5, 7, 9, 20 y 40 el tiempo mínimo es de 170 segundos.
    Siempre debemos ir sumando de menor a mayor.

  2. Gualterio permalink

    Hoola!

    Pues diría casi lo mismo que Borja. Pero el caso de 4, 5, 6 y 7 no me sale igual. Me da 44 segundos:

    Sumamos 4 + 5 => Coste 9
    Sumamos 6 + 7 => Coste 13
    Sumamos 9 + 13 => Coste 22

    Coste total: 44

  3. joti permalink

    Pues en el primer caso me da tiempo minimo 33 segundos, en el segundo caso 46 segundos. 4+5=9 9+6=15 15+7=22 —–> 22+9+15=46.

    El tercer caso 170 también.

    Nos vemos.

  4. Tengo problemas para subir el programa a la UVA. Pero este es el codigo (en java):

    public class Ej1 {

    public static void main(String[] args) {
    int solucion = 0;
    int suma = 0;
    java.util.Scanner tecla = new java.util.Scanner(System.in);
    int numNumeros = Integer.parseInt(tecla.nextLine());
    while (numNumeros != 0) {
    solucion = 0;
    String[] Snumeros = tecla.nextLine().split(” “);
    int[] numeros = new int[numNumeros];
    for (int i = 0; i < Snumeros.length; i++) {
    numeros[i] = Integer.parseInt(Snumeros[i]);
    }
    java.util.Arrays.sort(numeros);
    suma = numeros[0] + numeros[1];
    solucion += suma;
    for (int i = 2; i < numeros.length; i++) {
    suma = suma + numeros[i];
    solucion += suma;
    }
    System.out.println(solucion);
    numNumeros = Integer.parseInt(tecla.nextLine());
    }
    }
    }

    • Hola Ángel,

      Supongo que tendrás problemas para subirlo porque el juez de la UVa es un poco más pijotero que el DOMJudge que usamos en ProgramaMe en lo referente a Java. La clase tiene que llamarse Main y no debe ser “public”. Es decir el código debe empezar con:

      class Main {

      Si lo subes, ya no te dará un CompilationError o un Runtime Error. Pero la solución no está bien, y recibirás un Wrong Answer… no has resuelto correctamente la parte del acertijo 😉

      El domingo desvelamos cómo es (aunque sin código).

      Un saludo.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: