Overview

This problem asks you to choose the front direction (pillar number) of a streetlight so that the maximum “deviation angle (= shortest distance along the circumference)” to all pillars with benches is minimized.
The conclusion is: find the “largest empty gap where no bench exists,” and the answer is half of the arc on the opposite side of that gap.

Analysis

Key Insight 1: Think in terms of “pillar distance (number of pillars)” instead of angles

The deviation angle is
\(d(i,j)\times \frac{360}{N}\) degrees
so what we essentially need to minimize is the maximum of \(d(i,S_k)\) (how many pillars apart). We just multiply by \(\frac{360}{N}\) at the end.

Key Insight 2: Consider the “shortest arc containing all benches”

Having a maximum distance of \(r\) (pillars) when facing pillar \(i\) means that all benches fit “within \(r\) pillars to the left and right of \(i\).”
In other words, on the circumference, all benches must fit within a single arc of length at most \(2r\) (pillars).

Conversely, if all benches fit within an arc (contiguous interval) of length \(L\) (pillars), then by choosing the pillar near the middle of that arc as the front direction, the maximum distance is roughly half, and the minimum maximum distance is
\(r=\left\lceil \frac{L}{2}\right\rceil\)
(ceiling is needed since pillar numbers are integers).

Therefore, the problem transforms to: - Minimize the arc length \(L\) that contains all benches, - The answer is \(r=\lceil L/2\rceil\)

Key Insight 3: The shortest arc is “the opposite side of the maximum gap”

Sort the bench positions along the circumference and consider the gaps between adjacent benches (clockwise).
Among the intervals with no benches, let \(G\) be the longest interval (maximum gap). Using that as the “cut point” to open the circle, the remainder is the shortest arc containing all benches.

• Total circumference length: \(N\)
• Maximum gap: \(G\)
• Shortest arc length containing all benches: \(L_{\min}=N-G\)

Therefore, the minimum maximum distance is
\(r=\left\lceil \frac{L_{\min}}{2}\right\rceil\)

Concrete Example

When \(N=10\) and benches are at \(\{2,4,9\}\) (already sorted):
The gaps are: - \(4-2=2\) - \(9-4=5\) - Wrap-around: \(10+2-9=3\)

Maximum gap \(G=5\)
\(L_{\min}=10-5=5\)
\(r=\lceil 5/2\rceil=3\)
So the minimum deviation angle is \(3\times 360/10=108\) degrees.

Why a Naive Solution Doesn’t Work

There are \(N\) candidate pillars (up to \(10^9\)), so brute-force enumeration is impossible.
However, since the number of benches \(M\) is at most \(2\times 10^5\), we can solve it in \(O(M\log M)\) by just looking at the “gaps between benches.”

Algorithm

1. Sort the bench position array \(S\).
2. Scan the gaps between adjacent benches \(S[i+1]-S[i]\) and take the maximum.
3. Also compare the wrap-around gap \(N+S[0]-S[-1]\) to obtain the maximum gap \(G\).
4. Set \(L_{\min}=N-G\) and compute \(r=\lceil L_{\min}/2\rceil = (L_{\min}+1)//2\).
5. The answer angle is \(\dfrac{r\cdot 360}{N}\). Reduce the fraction using \(\gcd\) and output in P/Q format.
6. When \(M=1\), we can set the front direction to that pillar, so \(r=0\) (answer is 0/1).

Complexity

• Time complexity: \(O(M\log M)\) (dominated by sorting)
• Space complexity: \(O(M)\) (storing bench positions)

Implementation Notes

• If you forget the wrap-around gap \(N+S[0]-S[-1]\), you cannot handle the circular structure and will get WA.

• The minimum maximum distance is an integer number of pillars, so compute \(r=\lceil L/2\rceil\) as (L+1)//2.

• The final output \(\dfrac{r\cdot 360}{N}\) must be in reduced fraction form (reduce using gcd).

  Source Code

import sys
from math import gcd

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, M = data[0], data[1]
    S = data[2:2+M]
    S.sort()

    if M == 1:
        r = 0
    else:
        max_gap = 0
        for i in range(M - 1):
            gap = S[i + 1] - S[i]
            if gap > max_gap:
                max_gap = gap
        wrap_gap = N + S[0] - S[-1]
        if wrap_gap > max_gap:
            max_gap = wrap_gap

        L_min = N - max_gap
        r = (L_min + 1) // 2  # ceil(L_min/2)

    num = r * 360
    if num == 0:
        print("0/1")
        return
    den = N
    g = gcd(num, den)
    num //= g
    den //= g
    print(f"{num}/{den}")

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.