← 返回题目列表

AtCoder · awc0111_b

B. 圆形公园的路灯

中文机器翻译题面 查看原题

分数: 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