UOJ Logo Universal Online Judge

UOJ

#781. 新年的平衡兔环

附件下载 统计

众所周知,粉兔是一种非常团结的生物,它们非常喜欢聚在一起玩一种类似跷跷板的游戏:拉比特法环。

具体来说,在平面上有一个圆环$F=\{(x,y)|r^2\leqslant x^2+y^2\leqslant R^2\}, x,y\in \mathbb{R}$,而一只粉兔可以被视作平面上的一个质点,粉兔们质量不一,分别为$a_1,a_2,...,a_n$,共 $n$ 只粉兔。

由于粉兔们有着严格的体重控制和优秀的作息,粉兔们可以找到一种安排位置的方式,使得它们的重心恰好在原点。

具体来说,存在一长为 $n$ 的坐标序列 $(x_i,y_i)\in F$ 使得 $\displaystyle \sum_{i=1}^n a_ix_i = \sum_{i=1}^n a_iy_i =0$。

不幸的是,因为混入了每天晚睡早起卷多项式的粉免,这一性质被破坏了!

你觉得这是一个识别粉免的好办法,于是你测量了所有粉兔的质量,找到了圆环的参数 $r,R$,想要知道是否存在一种安排位置的方法。

输入格式

第一行三个非负整数 $n,r,R$,表示粉兔的数量,圆环的内径和外径。

第二行 $n$ 个非负整数 $a_i$,表示每只粉兔的质量。

输出格式

一行一个字符串,如果存在一种安排位置的方案就输出 YES,否则输出 NO

样例一

input

2 10 10
6 7

output

NO

explanation

此时圆环面退化为圆环,可以发现无论怎样放置粉兔,都无法达到平衡。

样例二

input

2 0 9
2 9

output

YES

explanation

将两只粉兔放在$(0,0)$即可。

样例三

input

4 10 10
4 2 2 4

output

YES

explanation

将第一二只粉兔放在$(10,0)$,三四只粉兔放在$(-10,0)$。

样例四

input

4 1 2
2 3 4 7

output

YES

数据范围与提示

对于所有数据,$1\leqslant n\leqslant 10^5,0\leqslant a_i\leqslant 10^4,0\leqslant r\leqslant R\leqslant 10^9$。

子任务编号 特殊性质 分值
$1$ $r=0$ $20$
$2$ $r\leqslant 10^3,R=10^9$ $20$
$3$ $n=2$ $20$
$4$ $n=3$ $20$
$5$ $20$

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$