← 返回题目列表

AtCoder · ahc037_a

A. 苏打水

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

故事

您在一家饮料厂工作。 在这家工厂中,制备大量的饮用水,并通过添加糖浆和二氧化碳制成最终产品碳酸饮料。 通过改变糖浆和二氧化碳的添加量,可以生产多种碳酸饮料。 此外,还可以将糖浆或二氧化碳添加到已制成的饮料中以制成其他变体。

给定您想要制作的饮料的所需甜度和碳酸化水平的多种组合,找到一种有效的方法来生产它们。

问题陈述

的 甜蜜 和 碳酸化水平 饮料的 由非负整数表示。 带有甜味的饮料 x 和碳酸化水平 y 表示为 (x, y).

最初你只有饮料 (0, 0)。 下面我们写 S 用于已制作的一组饮料。 最初 S = \{(0, 0)\}.

您可以重复以下操作来制作多种饮料。

  • 选择一种已经做好的饮料 (x, y) \in S.
  • 选择整数 x', y' 这样 x' \ge x 和 y' \ge y.
  • 分饮料 (x, y) 放入两个容器中,并保留其中一个。 制作新饮料 (x', y') 另加入适量糖浆和二氧化碳。 添加 (x', y') to S.
    • 请注意 (x, y) 将 不 被删除 S.
  • 此操作成本 (x' - x) + (y' - y).

鉴于 N 饮料 输入 (A_1, B_1), \dots, (A_N, B_N) ,最多可以执行上述操作 5N 次。 查找制作所有指定饮料的操作序列(即,满足以下条件的操作序列) (A_i, B_i) \in S 适用于所有人 i \in \{1, 2, \dots, N\} 在所有操作之后)总成本尽可能小。 允许制作在此过程中不存在于输入中的饮料。

评分

让 C 是总成本,并且 L = \max\{A_1, B_1, A_2, B_2, \dots, A_N, B_N\}。 那么分数由下式给出 \mathrm{round}\left(10^6 \times \frac{NL}{1 + C}\right).

有 150 测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。


输入

输入是从标准输入按以下格式给出的:

N
A_1 B_1
\vdots
A_N B_N

所有值均为整数,并且输入满足以下约束:

  • N = 1000
  • 0 \le A_i < 10^9
  • 0 \le B_i < 10^9
  • A_1, A_2, \dots, A_N 成对不同
  • B_1, B_2, \dots, B_N 成对不同
  • 存在 i 这样 A_i = 0
  • 存在 i 这样 B_i = 0

输出

让 M 是操作次数,并假设 m-th 操作使得 (x'_m, y'_m) 来自 (x_m, y_m)。 然后,按以下格式输出到标准输出:

M
x_1 y_1 x'_1 y'_1
\vdots
x_M y_M x'_M y'_M

所有值都应为整数,并满足以下条件:

  • 0 \le M \le 5N
  • 0 \le x_m \le x'_m < 10^9 和 0 \le y_m \le y'_m < 10^9
  • if (x_m, y_m) \ne (0, 0),则存在 k < m 这样 (x_m, y_m) = (x'_k, y'_k)
  • if (A_i, B_i) \ne (0, 0),则存在 m 这样 (A_i, B_i) = (x'_m, y'_m)

可以证明,如果存在一系列具有成本的操作 C 满足所有条件,除了 M \le 5N,则存在一个成本最多的操作序列 C 满足所有条件,包括 M \le 5N.

显示示例

输入生成

让 N = 1000.

A_1, \dots, A_N 生成如下:

  • 让 a_1 = 0,并生成成对不同的整数 a_2, \dots, a_N 之间 1 (含)和 10^9 (独家)均匀随机。
  • 让 A_1, \dots, A_N 是随机排列 a_1, \dots, a_N.

B_1, \dots, B_N 以相同的方式生成。

工具(输入生成器和可视化工具)

请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。


示例输入 1

4
0 6
2 5
3 2
4 0

示例输出 1

6
0 0 2 0
0 0 0 6
2 0 4 0
2 0 2 2
2 2 3 2
2 2 2 5

这是出于说明目的的示例,不满足输入约束。

您想要制作的饮料是 (0, 6), (2, 5), (3, 2), (4, 0)。 让 S 是已经制作好的一组饮料,如问题陈述中所示。

  • 第一个操作使 (2, 0) 来自 (0, 0)和成本 2.
    • 此操作后, S = \{(0, 0), (2, 0)\}.
  • 第二次操作使 (0, 6) 来自 (0, 0)和成本 6.
    • 此操作后, S = \{(0, 0), (2, 0), (0, 6)\}.
  • 第三次操作使 (4, 0) 来自 (2, 0)和成本 2.
    • 此操作后, S = \{(0, 0), (2, 0), (0, 6), (4, 0)\}.
  • 第四次操作使得 (2, 2) 来自 (2, 0)和成本 2.
    • 此操作后, S = \{(0, 0), (2, 0), (0, 6), (4, 0), (2, 2)\}.
  • 第五次操作使 (3, 2) 来自 (2, 2)和成本 1.
    • 此操作后, S = \{(0, 0), (2, 0), (0, 6), (4, 0), (2, 2), (3, 2)\}.
  • 第六次操作使 (2, 5) 来自 (2, 2)和成本 3.
    • 此操作后, S = \{(0, 0), (2, 0), (0, 6), (4, 0), (2, 2), (3, 2), (2, 5)\}.

最后, S 包含所有 (0, 6), (2, 5), (3, 2), (4, 0),所以这个输出会被判断为 AC.

总成本为 16。 自从 C = 16, L = 6, N = 4,得分为 \mathrm{round}\left(10^6 \times \frac{6 \times 4}{1 + 16}\right) = 1411765.