Distanciamiento social
Descripción
El doctor OCI-Cub está preocupado por la salud de sus pacientes después de un brote de la altamente contagiosa enfermedad humana COVID-19.
Para limitar la transmisión de la enfermedad, los pacientes del doctor OCI-Cub han decidido practicar "distanciamiento social" y distribuirse por toda la provincia.
La provincia tiene forma de recta numérica unidimensional, con intervalos disjuntos en los que hay césped para ellos.
Los pacientes quieren posicionarse en distintos puntos enteros, todos con césped, tal que se maximice el valor de , donde representa la distancia entre el par más cercano de pacientes.
Tarea
Determina el máximo valor posible de .
Entrada
La primera línea de contiene y .
Cada una de las siguientes líneas contienen dos enteros y , el inicio y fin de cada intervalo, ningún par de intervalos se cruza ni se toca en los extremos, un paciente parado en alguno de los extremos se considera que está dentro del césped.
Salida
Imprime el máximo valor de tal que todos los pares de pacientes estén a distancia al menos , se garantiza que una solución con existe.
Restricciones
Subtareas
Casos 2-3:
Casos 4-10: Sin restricciones adicionales
Entrada ejemplo
5 3
0 2
4 7
9 9
Salida ejemplo
2
Una forma de obtener es poner a las pacientes en las posiciones 0, 2, 4, 6 y 9.
Comments