Overview

This problem involves \(N\) pillars arranged in a circular ring, with \(M\) benches placed at certain pillar positions. The goal is to minimize the “maximum distance (angle) to any bench” when installing a streetlight at one of the pillars.

By organizing the positional relationships on the circular ring and focusing on the “largest gap” where no benches are placed, we can efficiently find the minimum cost.

---

Analysis

1. Intuitive Understanding (Unrolling the Circle into a Line)

Let’s cut the circular park at a point where there is no bench and think of it as a straight line.

To illuminate all benches, we need to install the streetlight so that it covers the range where benches exist. To minimize the maximum distance from the streetlight to any bench, the optimal strategy is to place the streetlight at exactly the center of the range where benches exist.

For example, if the distance (number of pillars) from the leftmost to the rightmost bench in the interval is \(L\), placing the streetlight at the center results in a distance of approximately \(\frac{L}{2}\) to the benches at both ends.

2. Finding the “Largest Gap”

On the circular ring, to make the range containing all benches as narrow (compact) as possible, we should install the streetlight so that it avoids the widest gap between adjacent benches (the largest gap) and covers everything else.

Let \(G\) be the largest gap among all gaps between adjacent benches. Then, all benches fit within an arc (interval) of length \(L = N - G\), obtained by subtracting \(G\) from the circumference \(N\).

Consider the maximum distance \(D\) (in terms of number of pillars) to the farthest bench when placing the streetlight at the center of this interval of length \(L\).

• When \(L\) is even: By placing at the central pillar, the distance to both ends is \(\frac{L}{2}\), so the maximum distance is \(D = \frac{L}{2}\).
• When \(L\) is odd: By placing at either of the two central pillars, the distance to the farther end is \(\frac{L+1}{2}\), so the maximum distance is \(D = \frac{L+1}{2}\).

Using integer floor division, both cases can be expressed with a single formula: $\(D = \lfloor \frac{N - G + 1}{2} \rfloor\)$

3. Concrete Example

Suppose \(N = 10\) with benches at positions \(1, 4\) (\(M = 2\)).

• The gaps between benches are:
  • Between \(1\) and \(4\): \(4 - 1 = 3\)
  • Between \(4\) and \(1\) (wrapping around the ring): \(10 - 4 + 1 = 7\)
• The largest gap is \(G = 7\).
• The length of the smallest interval containing all benches is \(L = N - G = 10 - 7 = 3\) (the interval from bench \(1\) to bench \(4\)).
• We place the streetlight near the center of this interval, at pillar \(2\) or \(3\).
  • When the streetlight is at \(2\), the distance to bench \(1\) is \(1\) and the distance to bench \(4\) is \(2\), giving a maximum distance of \(D = 2\).
• Applying the formula: \(D = (10 - 7 + 1) // 2 = 2\), which matches.

4. Conversion to Angle and Fraction

The desired cost is the minimum maximum distance \(D\) multiplied by \(\frac{360}{N}\). $\(\text{Cost} = D \times \frac{360}{N} = \frac{360 \times D}{N}\)$

To output this value as a reduced fraction, let the numerator be \(P' = 360 \times D\) and the denominator be \(Q' = N\), then divide both by their greatest common divisor (GCD) to obtain the answer in the form P/Q.

---

Algorithm

1. Handle special cases:
   • If there is only \(1\) bench (\(M = 1\)), we can place the streetlight at the same position as that bench, making the cost \(0\). Output 0/1 and terminate.
2. Sort:
   • Sort the bench positions \(S\) in ascending order.
3. Compute the maximum gap \(G\) between adjacent benches:
   • Calculate the differences \(S_{i+1} - S_i\) between adjacent elements in the sorted array.
   • Also calculate the wrap-around gap (between the last bench \(S_{M-1}\) and the first bench \(S_0\)): \(N - S_{M-1} + S_0\).
   • Let \(G\) be the maximum of all these values.
4. Compute the minimum maximum distance \(D\):
   • Calculate \(D = (N - G + 1) // 2\).
5. Convert to reduced fraction and output:
   • Let the numerator be \(P' = 360 \times D\) and the denominator be \(Q' = N\).
   • Find \(g = \gcd(P', Q')\), then let \(P = P' / g\) and \(Q = Q' / g\), and output in the format P/Q.

---

Complexity

• Time complexity: \(O(M \log M)\)

  • Sorting the bench positions takes \(O(M \log M)\).
  • Computing adjacent gaps takes \(O(M)\), and computing the greatest common divisor (Euclidean algorithm) takes \(O(\log N)\).
  • Since \(M \le 2 \times 10^5\), this runs well within the time limit.

• Space complexity: \(O(M)\)

  • \(O(M)\) memory is used for the array \(S\) storing bench positions.

---

Implementation Notes

• Handling the circular wrap-around: In the sorted array, the distance between the last element \(S[-1]\) and the first element \(S[0]\) is computed as \(N - S[-1] + S[0]\). Forgetting this would reduce the problem to a linear one instead of a circular one, so care must be taken.

• Using the Greatest Common Divisor (GCD): In Python, math.gcd can be used to easily reduce a fraction to its lowest terms.

  Source Code

import sys
import math

def solve():
    # 入力を高速に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    S = [int(x) for x in input_data[2:]]
    
    if M == 1:
        print("0/1")
        return
    
    # ベンチの位置をソート
    S.sort()
    
    # 隣り合うベンチの最大の間隔を求める
    max_gap = 0
    for i in range(M - 1):
        gap = S[i+1] - S[i]
        if gap > max_gap:
            max_gap = gap
    # 円環のつなぎ目の間隔
    gap = N - S[-1] + S[0]
    if gap > max_gap:
        max_gap = gap
        
    # 最小の最大距離 D
    D = (N - max_gap + 1) // 2
    
    # コストは D * 360 / N
    P_prime = 360 * D
    Q_prime = N
    
    # 既約分数にする
    g = math.gcd(P_prime, Q_prime)
    P = P_prime // g
    Q = Q_prime // g
    
    print(f"{P}/{Q}")

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.