← 返回题目列表

AtCoder · stpc2025_2_o

O. 下一个STPC

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

配点 : 100 点

問題文

STPC(东京科学编程竞赛)是由东京科学大学的学生举办的竞赛。首次举行是 2025 年 11 月 8 进行了。赶快来决定下次 STPC 的行程吧!

正整数 N,L,W 和 按字典顺序比较 N 正整数 找出满足以下条件的 D_1,D_2,\dots, D_N 。 对于

你正在尝试决定名为 STPC 的活动的举办日程。具体来说,是要决定正整数 X ,计划从今天起在 X 天后举办 STPC。

现在,已有的重大活动日程为 N 件。 i 第一个活动已知将在从今天起 D_i 天后举行。

你决定为了避免与这些活动日程重叠,来决定 STPC 的举办日程。也就是说,需要满足任何 i 反对 D_i\neq X 的条件。此外,由于准备需要时间,所以需要X\ge L 。此外,由于举办会场的原因,必须是X 是 您也可以写 W 的倍数。

在设定STPC开业日期以满足上述所有条件时,请注明最早开业日期为从今天起的天数。 即满足所有条件的最小正整数 X 。

然而,在这种情况下, X 存在。 如果正确答案是满足

制約

  • 所有输入均为整数
  • 1\le N\le 2\times 10^5
  • 1\le L,W\le 10^9
  • 1 \le D_1 \lt D_2 \lt \dots \lt D_N \le 10^9

入力

输入按以下格式给出。

N L W
D_1 D_2 \dots D_N

出力

打印答案。 来自


入力例 1

5 3 2
1 3 4 7 9

出力例 1

6

在这个输入示例中, L = 3, W = 2 。

  • X = 1 是 您也可以写 X \ge L 不符合要求。 它不是
  • X = 2 是 您也可以写 X \ge L 不符合要求。 它不是
  • X = 3 是 您也可以写 W 的倍数。
  • X = 4 是 您也可以写 3 这和第一个事件有重叠。
  • X = 5 是 您也可以写 W 的倍数。
  • X = 6 符合所有条件。

因此,最早的开业日期是 6 是后天。


入力例 2

10 1 1
1 2 3 4 5 6 7 8 9 10

出力例 2

11