← 返回题目列表

Codeforces · 2172/C

C. 圆圈彼此相距甚远

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

给你 $$$n$$$ 个圆圈和两个整数参数 $$$k$$$ 和 $$$\ell$$$。第 $$$i$$$ 个圆的半径为 $$$r_i$$$,并且 $$$r_i \ge r_j$$$ 对于每个 $$$1 \le i \lt j \le n$$$ 成立。任务是在 2D 平面上绘制这些 $$$n$$$ 圆,以便同时满足以下条件。在讨论条件之前,让我们回顾一下:

  • 每个圆都由其圆心 $$$O$$$ 和半径 $$$r$$$ 唯一确定。
  • 半径为 $$$r$$$ 的圆定义为距圆心 $$$O$$$ 距离为的所有点的集合 正是 $$$r$$$。此任务中考虑的所有距离都是欧几里德距离。
  • 圆的内部区域定义为距圆心$$$O$$$ 的距离为的所有点的集合 小于 $$$r$$$。
  • 我们说一圈$$$C$$$ 附上 如果$$$C^\prime$$$的所有点都位于$$$C$$$的内部区域内,则另一个圆$$$C^\prime$$$。

您需要绘制这些 $$$n$$$ 圆圈以满足以下所有条件:

  1. 所有圆的中心共线。
  2. 任意两个中心之间的距离最多为$$$k$$$。
  3. 没有两个圆相交。
  4. 如果一个圆包含两个圆 $$$C$$$ 和 $$$C^\prime$$$,则 $$$C$$$ 包含 $$$C^\prime$$$ 或 $$$C^\prime$$$ 包含 $$$C$$$。

  5. 第一个 $$$\ell$$$ 圆圈 可能会也可能不会 被其他圆圈包围,而剩余的每个 $$$n - \ell$$$ 圆圈 必须 至少被一个圆圈包围。

满足上述所有条件的排列称为 可行。对于可行的排列 $$$\mathcal{A}$$$,定义其 质量 $$$d(\mathcal{A})$$$ 作为属于不同圆的任意两点之间的最小距离。

如果给定情况存在至少一种可行的安排,则输出所有可行安排中的最大可能质量。如果不存在可行的安排,则输出$$$0$$$。

样本输入 1 的可行安排。
一种安排是 不可行 用于示例输入 1。

输入

第一行包含三个整数$$$k$$$、$$$n$$$和$$$\ell$$$,分别代表圆心之间的最大距离、要​​绘制的圆的数量以及可能或可能不被其他圆包围的圆的数量。

第二行包含 $$$n$$$ 整数 $$$r_1, r_2, \ldots, r_n$$$,其中 $$$r_i$$$ 是第 $$$i$$$ 个圆的半径。

  • $$$1 \le k \le 10^9$$$
  • $$$2 \le n \le 10^5$$$
  • $$$1 \le \ell \le \min\{n, 200\}$$$
  • $$$1 \le r_i \le 10^9$$$
  • $$$r_i \ge r_j$$$ 对于每个 $$$1 \le i \lt j \le n$$$。

输出

如果不存在可行的安排,则输出单个整数$$$0$$$。

否则,按以下格式输出所有可行排列 $$$\mathcal{A}$$$ 中最大可能的质量 $$$d(\mathcal{A})$$$:

  • 如果 $$$d(\mathcal{A})$$$ 是整数,则将其输出为单个整数。
  • 如果 $$$d(\mathcal{A})$$$ 不是整数,则以有理形式 $$$a/b$$$ 输出,使得 $$$1 \le a, b \le 10^9$$$, $$$\gcd(a,b) = 1$$$,并且 $$$|d(\mathcal{A}) - a/b|$$$ 被最小化。如果多个此类表格满足约束条件,则打印任何一个。

示例

输入
复制

15 4 3
7 5 3 1

输出
复制

3

输入
复制

14 6 1
7 5 4 3 2 1

输出
复制

1

输入
复制

14 2 2
5 4

输出
复制

5

输入
复制

22 4 4
4 4 1 1

输出
复制

10/3

输入
复制

13 3 3
6 3 1

输出
复制

4

注意

示例1说明: 第一张图展示了一种可行的布置,其中每个圆圈及其中心都以独特的颜色显示。

在这种布置中,属于不同圆的任意两点之间的最小距离是$$$3$$$,并且见证该距离的两个点被标记为红点。因此,这种安排的质量是$$$3$$$,这是这种情况下所有可行安排中可能的最大质量。请注意,只有圆 $$$4$$$ 需要包含在另一个圆中,而其余圆可以包含也可以不包含。

第二张图显示了一种安排 不可行。在这种情况下,圆 $$$1$$$ 包围圆 $$$3$$$ 和圆 $$$4$$$,但这两个圆都不包围另一个圆,从而违反了条件 $$$4$$$。