故事
您在一家饮料厂工作。 在这家工厂中,制备大量的饮用水,并通过添加糖浆和二氧化碳制成最终产品碳酸饮料。 通过改变糖浆和二氧化碳的添加量,可以生产多种碳酸饮料。 此外,还可以将糖浆或二氧化碳添加到已制成的饮料中以制成其他变体。
给定您想要制作的饮料的所需甜度和碳酸化水平的多种组合,找到一种有效的方法来生产它们。
问题陈述
的 甜蜜 和 碳酸化水平 饮料的 由非负整数表示。 带有甜味的饮料 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 以相同的方式生成。
工具(输入生成器和可视化工具)
- 网页版:这比提供动画的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。
示例输入 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.