Identificador: asma-v
Introducción
Algo terriblemente equivocado ha sucedido con el nuevo acelerador de partículas (AP) del CERN, y los imanes han comenzado a producir una radiación extraña y mortal nunca antes vista. Tienes que colocar escudos pesados alrededor de los imanes para prevenir daños ambientales inauditos. El AP es un anillo con una sala de mandos e imanes colocados en varios puntos alrededor del perímetro. Las posiciones de los imanes son representadas como el número de metros que uno debe andar en dirección opuesta a las agujas del reloj, a partir de la sala de mandos, alrededor de la circunferencia, para alcanzar el imán. El anillo tiene R metros de circunferencia. Tienes varios escudos curvos para proteger, cada uno de ellos puede cubrir K metros de la circunferencia del anillo. Un solo escudo no es suficientemente grande para cubrir dos imanes que estén exactamente a K metros de distancia.
Tarea
Tu tarea es de determinar el número mínimo de escudos necesarios para cubrir todos los imanes. Cubrir un imán con más de un bloque es aceptable, pero cada imán debe estar cubierto.
Ejemplo
Consideremos un anillo de R = 10 metros de circunferencia, con imanes a 0, 9, 4 y 6 metros. Los escudos que protegen pueden cubrir 2 metros de la circunferencia del anillo. Por tanto, los imanes a 0 y 9 metros pueden ser cubiertos con un solo escudo, dado que el anillo es circular. Los otros dos imanes requieren dos escudos separados, dando una suma de tres bloques necesarios a proteger los imanes.
Entrada
La primera línea de entrada contiene tres enteros separados por espacios: R, la circunferencia del anillo; N, el número de imanes; y K, la longitud de la circunferencia del anillo que un escudo puede cubrir. Los siguientes N datos significan la ubicación Li de los imanes, dadas en una o más líneas.
Salida
Un solo entero: el número mínimo de bloques necesarios para cubrir todos los imanes.
Muestra de ejecución
Entrada
10 4 2
0 9 4 6
Salida
3
Restricciones
1 ≤ R ≤ 100000
1 ≤ N ≤ R
1 ≤ K ≤ min(100, R)
0 ≤ Li < R para toda i
Li ≠ Lj si i ≠ j
Prueba tu programa con los datos:
10 4 2
9 9.5 0.5 4