AT_ahc044_a.[AHC044A] Cleaning Up

某公司有 $N$ 名员工，每人被分配了从 $0$ 到 $N-1$ 的编号。你需要为每位员工 $i$（$0 \leq i \leq N-1$）决定整数 $a_i$ 和 $b_i$（允许 $a_i = b_i$），并按照以下规则分配每周的值日生：

• 第 1 周，由员工 $0$ 担任值日生。
• 之后的每一周，假设上一周的值日生是员工 $x$，且截至上周结束，员工 $x$ 已经被分配为值日生 $t$ 次，则本周的值日生按如下方式决定：
  • 如果 $t$ 是奇数：本周值日生为员工 $a_x$。
  • 如果 $t$ 是偶数：本周值日生为员工 $b_x$。

对于每个 $i$（$0 \leq i \leq N-1$），给定未来 $L = 500\,000$ 周内希望员工 $i$ 被分配为值日生的目标次数 $T_i$。实际分配给员工 $i$ 的次数记为 $t_i$，请尽量使总误差 $\left|t_0 - T_0\right| + \left|t_1 - T_1\right| + \cdots + \left|t_{N-1} - T_{N-1}\right|$ 尽可能小。

输入通过标准输入按以下格式给出。

$N$ $L$ $T_0$ $T_1$ $\cdots$ $T_{N-1}$

• 所有测试用例中，员工数 $N$ 固定为 $100$。
• 所有测试用例中，周数 $L$ 固定为 $500\,000$。
• $0 \leq T_i \leq 10\,000$。
• $T_0 + T_1 + \cdots + T_{N-1} = L$。
• 输入均为整数。

请按以下格式输出到标准输出。

$a_0$ $b_0$
$a_1$ $b_1$
$\vdots$
$a_{N-1}$ $b_{N-1}$

其中，若存在 $i$（$0 \leq i \leq N-1$）使得 $a_i$ 或 $b_i$ 不满足 $0 \leq a_i \leq N-1$ 或 $0 \leq b_i \leq N-1$，则判定为 WA。

查看示例

故事背景

某公司正在致力于打造更舒适的工作环境。从新员工入职的 4 月起，公司决定每周进行一次内部清扫。然而，值日生的分配并不简单。例如，不能让某个人负担过重，尤其是新员工的负担要特别少。此外，值日生的分配方式还要便于记忆，比如“X 之后是 Y 或 Z”。请尽量优化分配方式，使其尽量符合这些要求。

得分

若你输出的分配方式的总误差为 $E$，则得分为 $10^6-E$。保证得分不会为负。

共有 150 个测试用例，所有用例的得分之和为你的提交得分。如果有任意一个用例输出不合法或超时，则整份提交判为 WA 或 TLE。比赛期间以最高得分计入最终排名，赛后不再进行系统测试。若多名选手得分相同，则排名并列。

输入生成方法

记 $\mathrm{rand}(L, U)$ 为在 $L$ 到 $U$ 之间均匀随机生成一个整数，输入生成方法如下：

1. 对每个 $0 \leq i \leq N-2$，用 $T_i = \mathrm{rand}(0, 10000)$ 生成。
2. 计算总和 $S = T_0 + \cdots + T_{N-2}$，若 $0 \leq L-S \leq 10000$，则令 $T_{N-1} = L-S$ 并确定输入，否则回到第 1 步重新生成。

工具（输入生成器与可视化工具）

• 网页版：比本地版性能更高，支持动画显示。
• 本地版：需安装 Rust 语言 编译环境。
  • Windows 版编译好的二进制：如不方便配置 Rust 环境可直接使用。

比赛期间，禁止分享可视化结果、解法或讨论。请注意遵守。

由 ChatGPT 4.1 翻译