AT_ahc058_a [AHC058A] Apple Incremental Game

APPLE ARTIS社（通称 AA社）は、りんごの大量生産を生業とする企業である。このたび、長年の研究の成果により、無からりんごを生み出す革新的な機械の開発に成功した。 しかし、この機械を用いてりんごを本格的に大量生産するには、機械そのものを大量に生産する必要がある。そこでAA社は、りんご生産機を生産するための機械生産機、さらにその機械生産機を生産するための機械生産機生産機、というように階層的に機械を生み出す仕組みを構築した。 AA社のエンジニアであるあなたは、これらの階層的な機械群を活用し、できるだけ多くのりんごを生産するための生産計画アルゴリズムを構築する任務を任された。

共有 $N \times L$ 种类型的机器，由 $N$ 种 ID 与 $L$ 种 Level 组成。Level 为 $i$，ID 为 $j$ 的机器称为 **$j^i$ 号机器**（$0 \leq i < L,\ 0 \leq j < N$）。 $j^0$ 号机器的产能为 $A_j$。$j^i$ 号机器初始强化费用为 $C_{i,j}$。 你的目标是在 $T$ 轮结束后，最大化苹果的总数量，具体操作流程如下。 ## 生产计划流程 记 $B_{i,j}$ 为 $j^i$ 号机器的数量，初始时所有 $B_{i,j}$ 均为 1。记 $P_{i,j}$ 为 $j^i$ 号机器的强化次数，初始时所有 $P_{i,j}$ 均为 0。 计划开始时初始苹果数量为 $K$。每一轮请依照以下步骤进行： 1. 你可以选择以下两种操作之一： - 强化 $j^i$ 号机器：消耗 $C_{i,j} \times (P_{i,j} + 1)$ 个苹果，使 $P_{i,j}$ 增加 1。但若操作后苹果数量会小于 0，则不能强化。 - 什么都不做。 2. 对于所有 $j^i$ 号机器，按 Level 0, 1, 2, 3 的顺序，依次执行以下操作： - 若是 Level 0 的机器（$i=0$）： - 苹果数量增加 $A_j \times B_{i,j} \times P_{i,j}$。 - 若是 Level 1 及以上的机器（$i\geq1$）： - $B_{i-1,j}$ 增加 $B_{i,j} \times P_{i,j}$。 请选择合适的操作策略，在 $T$ 轮操作后最大化苹果数量。

输入以如下格式从标准输入给出。 > $N$ $L$ $T$ $K$ $A_0$ $A_1$ $\cdots$ $A_{N-1}$ $C_{0,0}$ $C_{0,1}$ $\cdots$ $C_{0,N-1}$ $C_{1,0}$ $C_{1,1}$ $\cdots$ $C_{1,N-1}$ $\vdots$ $C_{L-1,0}$ $C_{L-1,1}$ $\cdots$ $C_{L-1,N-1}$ - 第 1 行包含 4 个整数 $N, L, T, K$： - $N$ 为机器 ID 的种类数，且 $N=10$。 - $L$ 为机器 Level 的种类数，且 $L=4$。 - $T$ 为轮数，且 $T=500$。 - $K$ 为初始苹果数量，且 $K=1$。 - 第 2 行包含 $N$ 个用空格分隔的整数 $A_0, A_1, \dots, A_{N-1}$，代表各 Level 0 号机器的生产能力： - $A_j$ 表示 $j^0$ 号机器的产能，$1 \leq A_j \leq 100$。 - $A$ 单调递增排序（$A_0 \leq A_1 \leq \cdots \leq A_{N-1}$）。 - 接下来的 $L$ 行，每行含 $N$ 个用空格分隔的整数 $C_{i,j}$： - $C_{i,j}$ 表示 $j^i$ 号机器的初始强化费用，$1 \leq C_{i,j} \leq 1.25 \times 10^{12}$。

请输出恰好 $T$ 行，每行描述第 $t$ 轮（$0 \leq t < T$）的操作，按从第 0 轮至第 $T-1$ 轮顺序排列，格式如下： - 若选择强化 $j^i$ 号机器： > $i$ $j$ - 若选择什么都不做： ``` -1 ``` 程序输出中可以包含以 `#` 开头的注释行。

## 计分规则 记 $S$ 为 $T$ 轮结束后剩余苹果数量。你的得分计算方式为 $\mathrm{round}(10^5 \times \log_2 S)$。分数越高越好。 下列情况会被判定为输出错误（WA）： - 强化操作导致苹果数量小于 $0$ - 指定了不存在的机器 Level 或 ID - 操作数少于 $T$ 次 测试数据共有 $150$ 组，提交得分为所有测试用例得分之和。若输出非法或部分数据超时，则本次提交得分为 $0$。比赛最终排名以比赛期间最高有效得分排序，相同分数并列，不以提交时间排序。比赛结束后不进行系统测试。 ## 输入数据生成方式 $\mathrm{rand\_double}(L, U)$ 表示在 $[L, U]$ 上以均匀分布生成实数。 ### $A_j$ 的生成 - $j=0$ 时：$A_0=1$ - $j\neq0$ 时：$A_j=\mathrm{round}(10^{\mathrm{rand\_double}(0,2)})$ - 全部生成后将 $A$ 升序排列 ### $C_{i,j}$ 的生成 - $i=0$ 且 $j=0$：$C_{0,0}=1$ - 其他情况：$C_{i,j} = \mathrm{round}(A_j \times 500^i \times 10^{\mathrm{rand\_double}(0,2)})$ ## 工具（输入生成器与可视化工具） - [网页版](https://img.atcoder.jp/ahc058/UpvAVdx6.html?lang=zh)：带动画，可手动操作。功能较强大。 - [本地版](https://img.atcoder.jp/ahc058/UpvAVdx6.zip)：需安装 [Rust](https://www.rust-lang.org/) 编译环境。 - [Windows 预编译版](https://img.atcoder.jp/ahc058/UpvAVdx6_windows.zip)：如无 Rust 环境建议使用。 请注意，在比赛期间禁止分享可视化结果或讨论思路与解法。 由 ChatGPT 5 翻译