CF479D Long Jumps
题目描述
Valery 是 Berland 学校的一名体育老师。学生们将参加跳远测试,但 Valery 丢失了他最喜欢的尺子!不过,Valery 没有失落,因为他找到了另一把尺子,它的长度为 $l$ 厘米。这个尺子上已经有 $n$ 个刻度,可以用来进行测量。
我们假设这些刻度是按照从尺子起始到结束的顺序编号的。第一个刻度与尺子的起点重合,表示原点。最后一个刻度与尺子的末尾重合,距离原点为 $l$。这把尺子可以表示为一个递增的数列 $a_1, a_2, ..., a_n$,其中 $a_i$ 表示第 $i$ 个刻度离原点的距离 ($a_1=0, a_n=l$)。
Valery 认为,如果存在一对整数 $i$ 和 $j$ ($1 \leq i \leq j \leq n$),使得第 $i$ 个刻度和第 $j$ 个刻度之间的距离恰好等于 $d$,即 $a_j - a_i = d$,那么就可以用尺子测量 $d$ 厘米的距离。
根据规定,女生应该至少能够跳 $x$ 厘米,男生应该至少能够跳 $y$ 厘米 ($x < y$)。为了测试学生的能力,Valery 需要尺子能够测量出这两个距离 $x$ 和 $y$。
你的任务是确定最少需要增加多少个刻度,使得尺子能够测量这两个距离 $x$ 和 $y$。你可以在尺子上添加任何整数非负距离,且不超过尺子长度 $l$。
输入格式
- 第一行包含四个正整数 $n, l, x, y$ ($2 \leq n \leq 10^5, 2 \leq l \leq 10^9, 1 \leq x < y \leq l$),分别表示刻度数、尺子长度、女生跳远的标准和男生跳远的标准。
- 第二行包含一个递增的整数序列 $a_1, a_2, ..., a_n$,其中 $a_i$ 表示第 $i$ 个刻度到尺子起点的距离 ($0 = a_1 < a_2 < ... < a_n = l$)。
输出格式
- 输出一行,包含一个非负整数 $v$,表示需要增加的刻度数。
- 接下来一行,输出 $v$ 个空间分隔的整数 $p_1, p_2, ..., p_v$,表示新增加的刻度的距离。刻度可以按照任意顺序输出。如果有多个解,可以输出任意一个。
说明/提示
在第一个示例中,初始尺子无法测量 $230$ 厘米的距离。只需增加 $230$ 厘米的刻度,或者 $20$ 厘米的刻度就可以了。
在第二个示例中,尺子已经能够测量 $185$ 厘米和 $230$ 厘米的距离,因此无需增加新的刻度。
在第三个示例中,尺子只有初始和末尾两个刻度。为了能够测试学生的能力,我们需要增加 $185$ 和 $230$ 厘米的刻度。