AlgoMooc
← 返回题库

K0040. 魔法阵的预言时刻

简单通过率 47% · 提交 133 · 通过 63
模拟数学排序

小慕在维护一个古老的魔法系统时发现,每个魔法符文必须在特定的能量脉冲瞬间激活,否则会导致系统崩溃。 已知能量脉冲的首次发生时刻为 `s`,此后每隔 `d` 个时间单位会再次发生(即脉冲时刻为 `s, s+d, s+2d, s+3d, ...`)。现在有 `n` 个符文需要激活,第 `i` 个符文的激活时刻为 `t_i`(按输入顺序索引从 `0` 开始)。只有当符文的 `t_i` 某个能量脉冲时刻时,该符文才能成功激活。 请按能量脉冲的发生顺序,输出所有能成功激活的符文的索引。若同一脉冲时刻对应多个符文,则按它们在输入中的顺序输出。

提示:带虚线的词点一下有通俗解释。

输入描述

- 第一行输入整数 `n`(`1 <= n <= 1e5`)。 - 第二行输入 `n` 个整数 `t_1, t_2, ..., t_n`(`1 <= t_i <= 1e9`),表示每个咒语的施放时刻。 - 第三行输入两个整数 `s` 和 `d`(`1 <= s, d <= 1e9`),表示魔法阵的首次激活时刻和周期。

输出描述

- 输出一行整数,表示可施放咒语的索引,按魔法阵激活时刻的顺序排列。同一时刻的咒语按输入顺序输出。 - 如果输出数组为空,那么输出-1,

示例

示例 1

输入

4
2 7 12 17
2 5

输出

0 1 2 3

说明:魔法阵激活时刻为 `2, 7, 12, 17`,四个咒语的时刻均匹配,按顺序输出索引 `0,1,2,3`。

示例 2

输入

6
8 6 8 11 9 14
8 3

输出

0 2 3 5

说明:魔法阵激活时刻为 `8, 11, 14, 17...`(只需覆盖所有输入的 `t_i`)。 - `t=8` 的咒语索引为 `0` 和 `2`,按输入顺序输出。 - `t=11` 对应索引 `3`,`t=14` 对应索引 `5`。

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。