Mucche Arrabbiate (Argento)#10595
La mucca Bessie ha ideato quello che, a suo parere, diventerà il prossimo videogioco di successo: "Angry Cows" (Mucche Arrabbiate). La trama del gioco, che Bessie ritiene del tutto originale, è la seguente: il giocatore lancia mucche con una fionda in una scena unidimensionale, composta da numerosi covoni di fieno posizionati in vari punti della retta numerica. Ogni mucca atterra con una forza sufficiente a far esplodere i covoni di fieno situati nelle immediate vicinanze del punto di atterraggio. L'obiettivo del gioco è utilizzare diverse mucche per far esplodere tutti i covoni di fieno.
Sulla retta numerica sono posizionati covoni di fieno in punti interi distinti x_1, x_2, \ldots, x_n. Se una mucca viene lanciata con forza e atterra nel punto , si genera un'esplosione di raggio , che distrugge tutti i covoni di fieno situati all'interno dell'intervallo [x - r, x + r].
Per il lancio sono disponibili mucche, ciascuna delle quali ha la stessa forza . Determinare il valore intero minimo di per il quale, con queste mucche, è possibile far esplodere tutti i covoni di fieno.
Nella prima riga sono contenuti due numeri interi n~(1 \le n \le 50000) e k~(1 \le k \le 10). In ciascuna delle successive righe è contenuto un numero intero x_i~(0 \le x_i \le 10^9), che indica la posizione di uno dei covoni di fieno sulla retta numerica.
Stampare la forza minima con cui è necessario lanciare ciascuna mucca per far esplodere tutti i covoni di fieno.
Esempio 1