Problem Background

A long highway connects City B and City T, with existing road signs placed at certain points. Drivers often find the distance between consecutive signs too large. To quantify this issue, we define the "empty index" of the highway as the maximum distance between any two adjacent road signs.

Problem Statement

The local government plans to add up to K new road signs to minimize the highway's empty index. Your task is to determine the smallest possible value of the empty index achievable under this constraint. Note that the start and end of the highway are guaranteed to have signs, all existing and new signs must be placed at integer distances from the start, and the highway length is an integer.

Input Specifications

• First line: Three integers L, N, K, representing the total length of the highway, the number of existing signs, and the maximum number of new signs allowed to be added.
• Second line: N strictly increasing integers, each denoting the distance from the start to an existing road sign. All values lie within the interval [0, L].

Output Specifications

Output a single integer: the minimal possible empty index after adding up to K road signs.

Sample Input & Output

Sample Input

101 2 1
0 101

Sample Output

51

Explanation

Initially, only the start (0) and end (101) have signs. Adding one sign at either 50 or 51 splits the highway into segments of 50&51 or 51&50, resulting in an empty index of 51—this is the smallest feasible value.

Constraints

• 50% of test cases: 2 ≤ N ≤ 100, 0 ≤ K ≤ 100, 0 < L ≤ 10^7
• 100% of test cases: 2 ≤ N ≤ 100000, 0 ≤ K ≤ 100000, 0 < L ≤ 10^7

Scratch Solution Implementation

This problem is efficiently solved using a binary search algorithm. Below is the step-by-step implementation in Scratch:

1. Data Preparation

• Create variables: L, N, K, low, high, mid, best, needed_signs.
• Create two lists: sign_positions (to store existing sign distances) and gaps (to store distances between consecutive signs).
• Read input values into L, N, K, then populate sign_positions with the list of existing sign positions.

2. Calculate Gaps Between Existing Signs

• Use a loop to iterate through sign_positions:

  set i to 1
  repeat until i = length of sign_positions
    add (item (i+1) of sign_positions - item i of sign_positions) to gaps
    change i by 1
  

3. Binary Search Initialization

• Set low to 1, high to L, best to L.

4. Binary Search Execution

• Use a repeat until block with condition low > high:

  repeat until low > high
    set mid to ((low + high) // 2)
    set needed_signs to 0
    repeat each gap in gaps
      set needed_signs to needed_signs + ((gap - 1) // mid)
    if needed_signs ≤ K
      set best to mid
      set high to mid - 1
    else
      set low to mid + 1
  

5. Output Result

• Display the value of best as the minimal empty index.

Optimization Notes

• For large datasets, ensure list operations are efficient by avoiding unnecessary repetitions.
• Use integer division exclusively to prevent floating-point inaccuracies.