← 返回题目列表

AtCoder · ahc055_a

A. 弱点

中文机器翻译题面 查看原题

故事

《日本桥金银岛》是一部在虚构的 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))

工具(输入生成器和可视化工具)

请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。