Conexiones aeropuertarias P30228


Statement
 

pdf   zip

thehtml

En un país lejano todas las ciudades importantes se encuentran curiosamente en diversas posiciones de una misma carretera recta muy larga. Para mejorar los desplazamientos, el gobierno del país ha decidido conectar mediante vuelos directos todas las ciudades que se encuentren al menos a distancia d entre sí. ¿Cuál es la máxima d con la que es posible ir volando desde cualquier ciudad hasta cualquier otra, ya sea directa o indirectamente?

Entrada

La entrada consiste en diversos casos, cada uno con el número de ciudades n, seguido de n ‍enteros diferentes con la posición de cada ciudad pi. Podéis suponer n ≥ 2, 0 ≤ pi ≤ 108, y que las ciudades son comparativamente tan pequeñas que se pueden considerar como puntos en la recta.

Salida

Para cada caso, escribid la máxima d con la que se consigue que todo par de ciudades quede conectado mediante uno o más vuelos.

Puntuación

  • test-1:  ‍ Entradas donde la diferencia entre la posición máxima y la mínima es como mucho 10, como el Ejemplo.  ‍20 Puntos ‍
  • test-2:  ‍ Entradas donde n ≤ 200.  ‍30 Puntos ‍
  • test-3:  ‍ Entradas donde n ≤ 105.  ‍50 Puntos ‍
Public test cases
  • Input

    2  0 10
    5  30 25 33 23 29
    

    Output

    10
    6
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++