$N$ robots sont placés sur un cercle. La position la plus au nord porte le numéro $0$. On partage le cercle en $M$ parties égales ($M \ge N$) et on numérote les autres points de division de $1$ à $M-1$ dans le sens horaire. On définit ainsi les positions de $0$ à $M-1$ (figure 1). Initialement, les robots occupent $N$ positions distinctes.
La distance entre deux positions $x,y$ est définie par $y-x$ ($y \ge x$). Un robot $R_i$ situé en $x_i$ peut surveiller les points dans une portée fixe $R>0$ dans les deux sens. Si $a$ est la position à distance $R$ de $x_i$ dans le sens antihoraire et $b$ celle à distance $R$ dans le sens horaire, alors $R_i$ surveille la partie du cercle allant de $a$ à $b$ dans le sens horaire.
Nous voulons surveiller tout le cercle. Les positions initiales peuvent laisser certaines parties sans surveillance ; nous souhaitons alors déplacer les robots pour couvrir tout le cercle. Nous supposons $M \le 2RN$, ce qui garantit qu’un tel déplacement existe toujours.
Les robots ne peuvent se déplacer que vers les positions du cercle définies ci-dessus, et chaque robot peut se déplacer au plus une fois. Nous voulons minimiser la plus grande distance parcourue par un robot.
Par exemple, dans la figure 1, les trois robots $R_1,R_2,R_3$ sont respectivement aux positions $1,2,5$, et leur portée est $R=2$. Pour surveiller tout le cercle, $R_1$ se déplace à la position $0$ et $R_3$ à la position $6$. Ce déplacement minimise la plus grande distance parcourue.
Figure 1
Étant données les positions de $N$ robots, leur portée $R$ et l’entier $M$, trouvez et affichez la plus petite distance maximale de déplacement permettant de surveiller tout le cercle.
Entrée
L’entrée standard fournit les informations suivantes. La première ligne contient le nombre de robots $N$ ($1 \le N \le 1,000,000$). La deuxième contient deux entiers $R,M$ définissant la portée de surveillance et les positions du cercle ($1 \le R,M \le 10^9$, $N \le M \le 2RN$). La ligne suivante contient $N$ entiers distincts $x_i$ ($0 \le x_i \le M-1$, $i=1,\ldots,N$), séparés par des espaces, indiquant les positions initiales des robots.
Sous-tâches
Sous-tâche 1 : 10 points sur 100 ; $M \le 10$.
Sous-tâche 2 : 30 points sur 100 ; $N \le 7,000$.
Sous-tâche 3 : 60 points sur 100 ; aucune contrainte autre que celles d’origine.
Sortie
Affichez sur la sortie standard la plus petite distance maximale de déplacement des robots permettant de surveiller tout le cercle.
Exemples
Entrée 1
3 2 10 1 2 5
Sortie 1
1
Entrée 2
6 1 11 0 1 2 3 4 5
Sortie 2
2