AT_ahc044_a [AHC044A] Cleaning Up

ある会社では、現在働きやすい環境づくりを目指している。そこで新入社員が入社する 4 月から、社内の掃除を毎週行うことにした。 しかしながら、掃除当番は簡単に決められるものではない。 たとえば 1 人に負担をかけすぎてはならないことや、まだ仕事に慣れていない新入社員の負担は特に少なくしなければならないことなど、様々な制約がある。 また、掃除当番の決め方は「X さんの次は Y さんか Z さん」のように覚えやすいものでなければならない。 できるだけ制約通りになるように、掃除当番の決め方を最適化せよ。

某公司有 $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。 [查看示例](https://img.atcoder.jp/ahc044/PnJFT8lu.html?lang=ja&seed=0&output=sample)

### 故事背景 某公司正在致力于打造更舒适的工作环境。从新员工入职的 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 步重新生成。 ### 工具（输入生成器与可视化工具） - [网页版](https://img.atcoder.jp/ahc044/PnJFT8lu.html?lang=ja)：比本地版性能更高，支持动画显示。 - [本地版](https://img.atcoder.jp/ahc044/PnJFT8lu.zip)：需安装 [Rust 语言](https://www.rust-lang.org/ja) 编译环境。 - [Windows 版编译好的二进制](https://img.atcoder.jp/ahc044/PnJFT8lu_windows.zip)：如不方便配置 Rust 环境可直接使用。 比赛期间，禁止分享可视化结果、解法或讨论。请注意遵守。 由 ChatGPT 4.1 翻译