故事
《日本桥金银岛》是一部在虚构的 R 国中非常受欢迎的小说,而您是根据这部小说改编的游戏的忠实粉丝。在这个游戏中,出现了无数的宝箱。打开宝箱可以让你获得武器,你可以使用它在游戏中获得优势。
要打开宝箱,您必须徒手或使用武器攻击它。听说打开游戏中所有宝箱就能解锁秘密结局,你决定想办法用最少的攻击次数打开所有宝箱,希望能尽快看到结局。
问题陈述
有 N 宝箱,以及 i第一个宝箱叫宝箱 i (0 \le i \lt N)。宝箱初始硬度 i is H_i。宝箱 i 包含武器 i.
宝箱硬度时 i 减少为 0 以下,宝箱 i 打开,武器 i 变得可用。武器有耐久度,武器的耐久度 i is C_i.
你可以徒手或使用可用的武器攻击宝箱。
- 徒手攻击:攻击宝箱时 b 徒手,宝箱硬度 b 减少 1。徒手攻击次数没有限制。
- 用武器攻击:当你攻击宝箱时 b 带武器 w,宝盒硬度 b 减少 A_{w,b},以及武器的耐久度 w 减少 1。当武器的耐久度 w 达到 0,它损坏并且不能再用于攻击。
找到一系列攻击,以尽可能少的攻击打开所有宝箱。
评分
您的分数是 \( \sum_{i=0}^{N-1} H_i - T + 1 \),其中 T 是打开所有宝箱的攻击次数。
如果产生以下无效输出,则判断为 WA.
- 攻击已经打开的宝箱
- 使用尚不可用的武器进行攻击
- 使用耐久度已达到的武器进行攻击 0
- 输出无效的武器编号或宝箱编号
- 所有攻击完成后留下任何未打开的宝箱
有 150 测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。
输入
输入将从标准输入以以下格式提供。
\(
N \\
H_0 ~ H_1 ~ \ldots ~ H_{N-1} \\
C_0 ~ C_1 ~ \ldots ~ C_{N-1} \\
A_{0,0} ~ A_{0,1} ~ \ldots ~ A_{0,N-1} \\
A_{1,0} ~ A_{1,1} ~ \ldots ~ A_{1,N-1} \\
\vdots \\
A_{N-1,0} ~ A_{N-1,1} ~ \ldots ~ A_{N-1,N-1}
\)
- N 是宝箱的数量。它固定在 N = 200 在所有测试用例中。
- 第二行包含 N 空格分隔的整数 H_0, H_1, \ldots, H_{N-1} 代表宝箱的初始硬度。宝箱硬度 i is H_i,满意 100 \leq H_i \leq 500.
- 第三行包含 N 空格分隔的整数 C_0, C_1, \ldots, C_{N-1} 代表武器的耐久度。武器耐久度 i is C_i,满意 1 \leq C_i \leq 6.
- 以下 N 行各包含 N 以空格分隔的整数, A_{i, j}.
- A_{i,j} 代表宝盒硬度的数值 使用武器攻击时 j 减少 i,满意 1 \leq A_{i,j} \leq 500.
输出
让 T 是对宝箱的攻击总数。输出 T 行。
\(
W_{0}~B_{0}\\
\vdots \\
W_{T-1} ~ B_{T-1}
\)
对于每一行,输出武器索引 W_i 用于 i第次攻击和宝箱索引 B_i 受到攻击,按顺序,以空格分隔。如果 i第次攻击是徒手进行的, W_i 应输出为 −1.
输入生成
- \mathrm{rand}(L, U): 均匀地随机生成一个整数 L 和 U,包括在内。
- \mathrm{rand\_double}(L, U): 均匀地随机生成一个实数 L 和 U,包括在内。
生成 H_i, C_i,和 A_{i,j} (0 \le i \lt N, 0 \le j \lt N) 独立,如下: 数轴上的
- H_i = \mathrm{rand}(100, 500)
- C_i = \mathrm{rand}(1, 6)
- A_{i,j} = \mathrm{round}(500.0 / \mathrm{rand\_double}(1.0, 500.0))
工具(输入生成器和可视化工具)
- 网页版:这比提供动画的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。