Mucche Arrabbiate (Oro)#10598
La mucca Bessie ha ideato quello che, a suo parere, diventerà il prossimo videogioco di successo: "Angry Cows". La trama del gioco, che Bessie considera del tutto originale, è la seguente: il giocatore lancia una mucca con una fionda in una scena unidimensionale composta da numerose balle di fieno posizionate in vari punti della retta numerica. La mucca atterra con una forza sufficiente a far esplodere le balle di fieno che si trovano nelle immediate vicinanze del punto di atterraggio, il che, a sua volta, può innescare una reazione a catena che provoca l'esplosione di ulteriori balle di fieno. L'obiettivo del gioco è, usando un'unica mucca, innescare una reazione a catena che distrugga tutte le balle di fieno.
Sulla retta numerica si trovano balle di fieno in punti interi distinti x_1, x_2, \ldots, x_n. Se la mucca viene lanciata con una forza e atterra nel punto , si genera un'esplosione di raggio , che coinvolge tutte le balle di fieno situate all'interno dell'intervallo [x - r, x + r]. Queste balle di fieno esplodono quindi a loro volta (tutte simultaneamente), ciascuna con un raggio di esplosione pari a r - 1. Tutte le balle di fieno non ancora esplose che si trovano all'interno di queste zone di esplosione esplodono a loro volta (tutte simultaneamente) con un raggio di esplosione pari a r - 2, e così via.
Determinare la forza minima con cui è possibile lanciare un'unica mucca in modo che, atterrando in un punto opportuno, provochi infine l'esplosione di ogni balla di fieno presente nella scena.
La prima riga contiene un numero intero n~(2 \le n \le 50000). Ciascuna delle successive righe contiene un numero intero x_i~(0 \le x_i \le 10^9), che indica la posizione di una delle balle di fieno sulla retta numerica.
Stampare la forza minima con cui è necessario lanciare la mucca per far esplodere tutte le balle di fieno. La risposta deve essere arrotondata e stampata con esattamente una cifra dopo il punto decimale.
In questo esempio, una mucca lanciata con forza , ad esempio nel punto , fa esplodere immediatamente le balle di fieno nei punti e . Queste balle esplodono poi simultaneamente, ciascuna con un raggio di esplosione pari a , coinvolgendo le balle nei punti e . Queste balle esplodono poi simultaneamente con raggio , coinvolgendo l'ultima balla nel punto , che a sua volta esplode con raggio .
Esempio 1