No.1940 Escape through + -
タグ : / 解いたユーザー数 101
作問者 :
matcharate12
/ テスター :
Namu3
問題文
matcharate12君はどこか狭い一室に閉じ込められています。
その部屋から出るための鍵として、長さ $N$ の数列 $A$ があります。その数列の要素の総和を $S$ にすることで脱出することができるようです。
実はmatcharate12君は魔法使いで、数列の要素を変更することができます。
その魔法の効能は、具体的には以下のようになります。
この魔法は何回でも使うことが可能です。さらに、$1$ つの要素に対して好きなだけ魔法をかけることができます。
また $M$ はmatcharate12君によって既に定められています。
何回も同じ魔法を使うのは大変です。なのでそれで脱出できなかったら無駄な努力です。
与えられる数列に対して、matcharate12君は部屋から脱出することが可能かどうか判定してください。
入力
$N\ M\ S$ $A_1\ A_2\ \dots \ A_N$
・$1\le N\le 10^5$
・$1\le M\le 10^{18}$
・$1\le S\le 10^{18}$
・$1\le A_i\le 10^9$
・入力はすべて整数
出力
脱出することができるなら Yes 、できないなら No を出力してください。
サンプル
サンプル1
入力
4 2 10 1 1 1 1
出力
Yes
例えば $A_1,A_2,A_3$ に対して、$A_i+M$ に変える魔法を $1$ 回ずつかけると、魔法をかけた後の数列は $A=(1+2,1+2,1+2,1)=(3,3,3,1)$ になります。これは総和が $10$ と等しいので、matcharate12君は脱出することが可能です。よって Yes を出力します。
サンプル2
入力
2 2 5 1 3
出力
No
どう魔法をかけようと総和を $5$ にすることはできません。
サンプル3
入力
3 1 1000000007 1 2 5
出力
Yes
魔法を使用する回数が $10^9$ 回を超えることがあります。
サンプル4
入力
10 1414 1814 14 14 21 35 62 37 30 95 4 88
出力
Yes
入力例には挙げませんが、魔法を使用した後の数列の要素が $10^{18}$ を超えることがあることに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。