Piano Performance
Time limit2sMemory limit512 MB
Assign each of M notes to one of N fingers spaced K apart so the largest adjacent-note difficulty is minimized; output that minimum.
- Level
Medium7 of 10
- Topics
- Binary search, Greedy, Array, Implementation
- Solved
- No attempts yet
Statement
Sebin, who has N fingers, is the finest pianist and can play every piece with one hand.
The distance between two adjacent fingers of Sebin is always K. Therefore, if the distance between the i-th finger and the first finger is Xᵢ, then Xᵢ = (i-1)K holds (1 ≤ i ≤ N).
Sebin wants to play a piece made of M notes. Which finger plays each note can make the piece easier or harder.
Let Pᵢ be the pitch of the i-th note, and suppose this note is played with the Fᵢ-th finger. The difficulty of playing the i-th note and the adjacent (i+1)-th note is |(Pᵢ₊₁ - Pᵢ) - (X_Fᵢ₊₁ - X_Fᵢ)|.
The difficulty of the piece is the maximum difficulty over adjacent pairs of notes. Write a program that decides which finger plays each note and minimizes the difficulty of the piece.
Input
The first line gives two natural numbers N and M, the number of Sebin's fingers and the number of notes in the piece, and a natural number K, the distance between two adjacent fingers, separated by spaces.
The second line gives M integers P₁, ..., P_M separated by spaces.
Output
On the first line, print the minimum difficulty of the piece.
Constraints
Every input satisfies the following conditions.
- 1 ≤ N ≤ 2 × 10⁵
- 2 ≤ M ≤ 2 × 10⁵
- 1 ≤ K ≤ 10⁹
- X_N ≤ 10⁹
- 1 ≤ Pᵢ ≤ 10⁹ (1 ≤ i ≤ M)