/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 333 点
問題文
高橋君は、円形の公園の管理人をしています。この公園の外周には等間隔に N 本の柱が立っており、柱には 1 から N までの番号が時計回りに付けられています。
公園の円の中心に街灯を 1 基設置する計画があります。この街灯は特殊な指向性を持ち、いずれかの柱の方向を正面として照らします。
街灯の正面方向を柱 i に設定したとき、柱 j に対するずれ角を次のように定義します。柱 i と柱 j を円の中心から見たとき、時計回り・反時計回りのうち小さい方の角度（度数法）をずれ角とします。柱は N 本が等間隔に並んでいるため、隣り合う柱の間の中心角は \frac{360}{N} 度です。柱 i から柱 j まで、時計回りに数えた柱の間隔と反時計回りに数えた柱の間隔のうち小さい方を d(i, j) とすると、
d(i, j) = \min\bigl(|i - j|,\; N - |i - j|\bigr)
であり、ずれ角は d(i, j) \times \frac{360}{N} 度です。
公園の外周にある N 本の柱のうち M 本にはベンチが設置されています。k 番目のベンチは柱 S_k の位置にあります（S_1, S_2, \ldots, S_M はすべて互いに異なります）。
街灯の正面方向を柱 1, 2, \ldots, N のいずれかに設定するとき、その設定のコストを「M 個のベンチが設置された柱それぞれに対するずれ角のうち、最大のもの」と定義します。すなわち、正面方向を柱 i に設定したときのコストは
\max_{1 \leq k \leq M} \; d(i, S_k) \times \frac{360}{N}
です。
高橋君は、コストが最小となるように街灯の正面方向を選びたいです。コストの最小値を求めてください。
ただし、答えは既約分数 \frac{P}{Q}（P \geq 0, Q \geq 1, \gcd(P, Q) = 1）の形で P/Q と出力してください。答えが 0 の場合は 0/1 と、答えが整数の場合は分母を 1 として P/1 の形で出力してください。
制約
- 2 \leq N \leq 10^9
- 1 \leq M \leq \min(N, 2 \times 10^5)
- 1 \leq S_k \leq N (1 \leq k \leq M)
- S_k はすべて互いに異なる
- 入力はすべて整数
入力
N M S_1 S_2 \ldots S_M
- 1 行目には、柱の総数を表す整数 N と、ベンチの数を表す整数 M が、スペース区切りで与えられる。
- 2 行目には、ベンチが設置されている柱の番号 S_1, S_2, \ldots, S_M が、スペース区切りで与えられる。
出力
コストの最小値を既約分数の形で P/Q と 1 行で出力せよ。ここで P は 0 以上の整数、Q は正の整数であり、\gcd(P, Q) = 1 を満たす。
入力例 1
8 3 1 3 6
出力例 1
135/1
入力例 2
12 2 4 10
出力例 2
90/1
入力例 3
25 7 2 5 9 14 18 21 24
出力例 3
144/1
入力例 4
1000000000 12 1 12345678 98765432 200000000 333333333 400000001 555555555 666666666 777777777 888888888 999999999 1000000000
出力例 4
3800000007/25000000
入力例 5
2 1 2
出力例 5
0/1
Score : 333 pts
Problem Statement
Takahashi is the caretaker of a circular park. Along the perimeter of this park, N pillars are placed at equal intervals, numbered from 1 to N in clockwise order.
There is a plan to install one street light at the center of the park's circle. This street light has a special directional property and illuminates facing the direction of one of the pillars.
When the front direction of the street light is set to pillar i, the deviation angle with respect to pillar j is defined as follows. When viewing pillars i and j from the center of the circle, the deviation angle is the smaller of the clockwise and counterclockwise angles (in degrees). Since the N pillars are equally spaced, the central angle between adjacent pillars is \frac{360}{N} degrees. Let d(i, j) be the smaller of the number of pillar intervals counted clockwise from pillar i to pillar j and the number counted counterclockwise. Then,
d(i, j) = \min\bigl(|i - j|,\; N - |i - j|\bigr)
and the deviation angle is d(i, j) \times \frac{360}{N} degrees.
Among the N pillars on the park's perimeter, M of them have benches installed. The k-th bench is located at pillar S_k (S_1, S_2, \ldots, S_M are all distinct).
When the front direction of the street light is set to one of the pillars 1, 2, \ldots, N, the cost of that setting is defined as "the maximum deviation angle among those for each of the M pillars with benches." That is, the cost when the front direction is set to pillar i is
\max_{1 \leq k \leq M} \; d(i, S_k) \times \frac{360}{N}
Takahashi wants to choose the front direction of the street light so that the cost is minimized. Find the minimum value of the cost.
The answer should be output in the form P/Q as an irreducible fraction \frac{P}{Q} (P \geq 0, Q \geq 1, \gcd(P, Q) = 1). If the answer is 0, output 0/1. If the answer is an integer, output it in the form P/1 with denominator 1.
Constraints
- 2 \leq N \leq 10^9
- 1 \leq M \leq \min(N, 2 \times 10^5)
- 1 \leq S_k \leq N (1 \leq k \leq M)
- All S_k are distinct
- All inputs are integers
Input
N M S_1 S_2 \ldots S_M
- The first line contains the integer N representing the total number of pillars and the integer M representing the number of benches, separated by a space.
- The second line contains the pillar numbers S_1, S_2, \ldots, S_M where benches are installed, separated by spaces.
Output
Output the minimum value of the cost as an irreducible fraction in the form P/Q on a single line. Here, P is a non-negative integer, Q is a positive integer, and \gcd(P, Q) = 1.
Sample Input 1
8 3 1 3 6
Sample Output 1
135/1
Sample Input 2
12 2 4 10
Sample Output 2
90/1
Sample Input 3
25 7 2 5 9 14 18 21 24
Sample Output 3
144/1
Sample Input 4
1000000000 12 1 12345678 98765432 200000000 333333333 400000001 555555555 666666666 777777777 888888888 999999999 1000000000
Sample Output 4
3800000007/25000000
Sample Input 5
2 1 2
Sample Output 5
0/1