← 返回题目列表

AtCoder · rcl_contest_2021_a

A. 巫师X之战

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

問題文

魔法师X现在正在与一大群怪物对峙。怪物有 N 只,排成一排。
每个怪兽都有实力,从左数起 i 第几只怪兽的实力该值应乘以 A_i 。

魔法师X可以使用的魔法只有一个,就是“强化”。
“强化”是一种魔法,可以将一只怪兽的实力提高另一只怪兽的实力数值。
具体来说,需要经过以下步骤。

  1. 实力选择一个你想变身的怪物。 这位蒙苏特从左侧位置 p 。
  2. 再选一个蒙苏塔尔。 这位蒙苏特从左侧位置 q 。此时 p = q 也被接受。
  3. p 第几只怪兽的实力变换为 \(A_{p} = (A_{p} + A_{q}) \% K\)。 这里,\% K 是 您也可以写 K 所得的余数。
    (K 在这个世界上 极限值为实力, 如果超过实力是 在 K 就会溢出)

巫师X也最大化“力量提升” 最多可施放 M 次。

仔细选择你想要应用“力量提升”的怪物,然后 使实力尽可能小,以便在战斗中给自己带来优势。

每个测试用例和该问题的分数计算如下:

  • 对于一个测试用例,分数使用以下公式计算: \[分数 = \text{ceil}\left(\sum_{i}(\log_{2}K - \log_{2}(A_{i} + 1))\right)\] 此外, 表示大于或等于\text{ceil}(x) 是 您也可以写 x 的最小整数。
    另外,在你施展完咒语后, 如果有一个或多个值不是 A 在 0 , 将M - (魔法を唱えた回数) 添加到分数中。
  • 总共 50 有些物品。 每个测试的总分即为该题目的总分。

入力

输入是按以下格式从标准输入给出的。
第一行是一个整数 写入 N, M, K 用空格分隔。在第二行 N 整数由空格分隔。

\(\begin{array}{lll}
    N & M & K\\
    A_{ 0 } & \ldots & A_{ N-1 }
  \end{array}\)
  • N 是怪物的数量, 满足N = 300 感到满意。
  • M 是 X 被施放的次数,M = 1000 感到满意。
  • K 是 您也可以写实力, 如果超过K = 10^8 感到满意。
  • A_{i} 从左起 代表 i 第几只怪兽的实力的整数,0 < A_{i} < K 感到满意。

出力

输出是 由 M 行下方,每行由空格分隔。 将 2 整数输出到标准输出。 必须满足

\(\begin{array}{lll}
    p_{0} &  q_{0} \\
    \vdots &  \vdots \\
  \end{array}\)
  • p_{i} 是 您也可以写 i 在“力量提升”的第1步中选择的怪物的位置, 必须满足0 ≤ p_i ≤ N - 1 。
  • q_{i} 是 您也可以写 i 在“力量提升”步骤的第2步中选择的怪物的位置,0 ≤ q_i ≤ N - 1 。
  • p_{i} = q_i 也很好。
  • 如果输出不满足上述约束, 。 对于

关于生成手刀刻

每个用例均由测试用例生成器生成。
测试用例生成器可从页面底部的链接获取。
各 A_{i} 的值为 独立于小于1 以上 K 的整数均匀随机选择。


入力例1

5 10 100
75 99 51 48 1
此案例仅供说明之用;输入约束( N = 300, M = 1000, K = 10^8)不满意。

出力例1

0 0
0 0
3 4
3 2
2 1
2 2
1 4
每次“通电”后 A 看起来像这样:
50 99 51 48 1
0 99 51 48 1
0 99 51 49 1
0 99 51 0 1
0 99 50 0 1
0 99 0 0 1
0 0 0 0 1
在本例中,得分公式为 \( \text{ceil}(4(\log_2(100) - \log_2(0+1)) + (\log_2(100) - \log_2(1+1))) \fallingdotseq \text{ceil}(32.21\cdots) = 33\)。 由于只有不到一个值不是
另外,在你施展完咒语后, 如果有一个或多个值不是 A 在 0 ,10 - 7 = 3 已添加到您的分数中,
最终,33 + 3 = 36 是您的分数。 请注意,您不能设置大于

关于分配

我们通过以下链接提供测试用例生成器、测试器、示例输入数据和可视化器。

测试用例生成器、测试器、示例输入数据、可视化工具 (zip)


展示台说明

我们准备了一个可视化工具,可以计算分数并可视化输入和输出文件的结果。

  • 该可视化工具是桌面版本 谷歌浏览器 和 Mozilla 火狐浏览器 已在最新版本的 上确认操作。我们不保证它适用于所有浏览器环境。
  • 此可视化工具上计算的分数不是本次比赛的分数。评分将通过在 AtCoder 上提交答案来完成。此外,在可视化工具上计算的分数并不能保证您在本次比赛中的分数。
  • 请注意,我们不能保证因使用此可视化仪而造成的任何损坏。

可视化工具也包含在发行版中,有关如何使用它的说明写在发行版的 README.html 中。

输入文件
输出文件
fps
命令
A_p 差异
分数 本实验的
另存为图像