Skip to content

Cruces en los torneo de tenis

by en 03/02/2014

¡Hola!

Este fin de semana, los tenistas españoles han perdido en la eliminatoria ante Alemania de la Copa Davis. Eso nos lleva a luchar por la permanencia, para poder volver a participar el año que viene. ¡Triste estreno de Carlos Moyá al frente de la selección!

Como seguramente sabéis, los torneos de tenis (y de muchos otros deportes) se organizan en eliminatorias, donde los jugadores se enfrentan los unos a los otros para ir pasando rondas. Lo más cómodo es que el número de participantes sea una potencia de dos, de tal forma que en cada paso se eliminan a la mitad de los participantes, hasta llegar a la final, donde “sólo puede quedar uno”. Por ejemplo, en un torneo con 8 participantes, numerados del 1 al 8, tendríamos tres rondas:

Cruces de un torneo de tenis con 8 participantes

Los organizadores de los torneos, normalmente colocan a los jugadores en el cuadro inicial de tal forma que los dos mejores jugadores de la ATP sólo puedan encontrarse en la final. ¡¡Sería muy malo para el torneo y el espectáculo que en la primera fase se enfrentaran Nadal y Djokovic!! Pero, ¿cómo lo consiguen?

Si tenemos un torneo de 8 rondas, y los jugadores numerados empezando en 1, ¿en qué ronda se enfrentarían, llegado el caso, los jugadores 5 y 6? ¿Y las parejas de jugadores 13 y 16, 15 y 18, 100 y 103, o 120 y 130?

¡Cuéntanos tus conclusiones en los comentarios! Y si das con la solución y quieres programarla, puedes probarla aquí.

Anuncios

From → Fáciles, Problemas

4 comentarios
  1. Gualterio permalink

    Qué acertijo más chulo! Y como siempre, muy de actualidad 🙂
    Aquí van mis apuestas:

    – Jugadores 5 y 6: ronda 1
    – Jugadores 13 y 16: ronda 2
    – Jugadores 15 y 18: ronda 5
    – Jugadores 100 y 103: ronda 3
    – Jugadores 120 y 130: ronda 8.

    Pero me tenéis mosqueado, porque no necesito para nada saber cuántas rondas hay en el torneo… ¿lo habré entendido todo mal?… 🙂

    • David permalink

      Muy bien hecho! =)
      Acompaño con mi python. http://www.codeskulptor.org/#user28_hxjsoVo2K418frO.py

      Intento responderte al porque no necesitas el número de rondas. El mayor de los números (representando jugadores) ya tiene implícitamente esa información, al ser un sistema binario. 99 y 102 pueden representarse solamente con 7 bits, osea que si hubiese solo 7 rondas estos jugadores jugarían igualmente.
      Un ejemplo:
      99 -> 1100011
      102 -> 1100110

      99 XOR 102 -> 0000101

      Uso 99 en vez de 100 y 102 en lugar de 103. Porque empezamos a contar desde 0, no desde 1. Y como ves el 1 más significativo en el XOR esta en la tercera posición (de menos a más significativa), que coincide con el número de ronda en el que se cruzaran.

      No se si me explico… seguro que el domingo los expertos lo explicarán mejor. =)

      Salu2,
      David

  2. Oscar permalink

    Bien, si alguno puede echarme una mano con este código lo agradecería :), parece que me da las soluciones bien peeeero…

    public class Main {

    /**
    * @param args the command line arguments
    */
    public static void main(String[] args) throws java.io.IOException {

    java.io.BufferedReader in
    = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    long j1;
    long j2;
    long ronda;
    String[] entrada;

    entrada = in.readLine().split(” “);

    ronda = 0;

    j1 = Long.parseLong(entrada[1]) – 1;
    j2 = Long.parseLong(entrada[2]) – 1;

    while(j1 != j2){

    j1 = j1 / 2;
    j2 = j2 / 2;
    ronda++;
    }

    System.out.println(ronda);

    System.exit(0);
    }
    }

    • Bueno, parece que nadie se anima, a si es que te contesto yo.

      Aunque tu código tiene buena pinta, sólo sirve para resolver una pregunta en cada ejecución (por ejemplo, en un torneo a 3 rondas, nos dice en cuál se enfrentan los jugadores 2 y 5). Sin embargo, los problemas normalmente son multicaso; eso significa que el programa debe responder a muchas preguntas similares, y acabar cuando ya no haya más.

      Fíjate en el “Sample Input” y “Sample Output” del problema (http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=4391). Si tu programa recibe como entrada las cuatro líneas que se muestran en el sample input, debe escribir exactamente las cuatro del sample output. Sin embargo, sólo escribe la primera, y termina. En http://www.programa-me.com/documents/Contesthowto.pdf tenemos una guía con plantillas de código para cada uno de los esquemas habituales de los problemas de los concursos y jueces on-line, por si te resulta de interés.

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: