Valor de Amistad.


Submit solution

Points: 100 (partial)
Time limit: 60.0s
Memory limit: 128M

Author:
Problem types
Allowed languages
C, C++, Java, Pascal, Python, VB

Un sociólogo de IslaGrande ha desarrollado una fórmula para calcular numéricamente el valor de la amistad que existe entre un grupo de N personas. Para esto ha caracterizado a cada miembro del grupo con un valor entero y ha formado un conjunto S con estos valores enteros.

El valor de amistad del grupo es un valor A, miembro de este conjunto S, el cual produce la mínima mediana de distancias entre el valor A y los demás elementos del conjunto S. En otras palabras, A es el valor para el cual la mediana del conjunto de las diferencias absolutas entre A y los demás elementos del conjunto S se hace mínima. El conjunto de las diferencias absolutas entre A y los demás elementos del conjunto es (|S_i - A|, donde S_i \neq A para todo elemento S_i que pertenezca a S).

La mediana de un conjunto de N elementos (N impar) es el número que aparece en la posición N/2 al ordenarse los elementos del conjunto.

Por ejemplo, si se tiene un grupo de 4 personas, caracterizadas con los valores 27, 3, 1, y 9 respectivamente, al aplicar la fórmula del sociólogo quedaría:

Si    Distancias absolutas  Distancias Ordenadas    Mediana de las distancias ordenadas

27       0  24  26 18           18 24 26                24
3        24  0  2  6            2  6  24                6
1        26  2  0  8            2  8  26                8
9        18  6  8  0            6  8  18                8

Por tanto, el valor A sería 3, el cual produce el conjunto de distancias absolutas de menor mediana (correspondiente a la segunda fila de la tabla).

Tarea

Hacer un programa que permita:

  • Leer el número N personas del grupo y los valores de caracterización de cada una ellas.
  • Encuentre el valor de amistad A del grupo.
  • Escribir el mejor valor de amistad A.

Entrada

La entrada contiene:

  • Línea 1: N, la cantidad de personas en grupo.
  • Línea 2: Los N valores de caracterización de cada una de las personas del grupo.

Salida

La salida ontiene en una sola línea un valor el cual corresponde al valor que produce el mejor valor de amistad A.

Restricciones

  • 1 \le N < 100,000; N es siempre par.
  • Los valores de caracterización de personas estarán entre -10^9 y 10^9
  • En el 30% de los casos de prueba, N \le 5000.

Ejemplo #1 de Entrada

4
27 3 1 9

Ejemplo #1 de Salida

3

Ejemplo #2 de Entrada

10
5 -3 -1 0 9 -4 8 7 2 -3

Ejemplo #2 de Salida

-1

Comments


  • -2
    rales  commented on Feb. 20, 2024, 1:37 p.m.

    easy