AT_ahc058_a.[AHC058A] Apple Incremental Game

共有 $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)})$

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

• 网页版：带动画，可手动操作。功能较强大。
• 本地版：需安装 Rust 编译环境。
  • Windows 预编译版：如无 Rust 环境建议使用。

请注意，在比赛期间禁止分享可视化结果或讨论思路与解法。

由 ChatGPT 5 翻译