分数: 333 分
问题陈述
高桥是一个圆形公园的管理员。沿着这个公园的周边, N 柱子等间隔放置,编号从 1 to N 按顺时针顺序。
计划在公园圆圈中心安装一盏路灯。这种路灯具有特殊的方向性,面向其中一根柱子的方向照明。
当路灯的正面方向设置为柱子时 i, 偏差角 关于支柱 j 定义如下。看柱子时 i 和 j 从圆心开始,偏离角度是顺时针和逆时针角度中较小的一个(以度为单位)。自从 N 柱子等距,相邻柱子之间的圆心角为 \frac{360}{N} 度。让 d(i, j) 是从支柱顺时针计数的支柱间隔数中的较小者 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 is
\max_{1 \leq k \leq M} \; d(i, S_k) \times \frac{360}{N}
高桥希望选择路灯的正面方向,以便将成本降至最低。找出成本的最小值。
答案应以以下形式输出 P/Q 作为不可约分数 \frac{P}{Q} (P \geq 0, Q \geq 1, \gcd(P, Q) = 1)。如果答案是 0,输出 0/1。如果答案是整数,则以形式输出 P/1 带分母 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
- 第一行包含整数 N 代表柱子总数和整数 M 代表长凳数量,以空格分隔。
- 第二行包含支柱编号 S_1, S_2, \ldots, S_M 安装了长凳,并用空格分隔。
输出
以不可约分数的形式输出成本的最小值 P/Q 在一行上。在这里, P 是一个非负整数, 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