問題一覧 > 通常問題

No.1940 Escape through + -

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 52
作問者 : matcharate12matcharate12 / テスター : Namu3Namu3
2 ProblemId : 7708 / 自分の提出
問題文最終更新日: 2022-05-18 20:29:17

問題文

matcharate12君はどこか狭い一室に閉じ込められています。
その部屋から出るための鍵として、長さ $N$ の数列 $A$ があります。その数列の要素の総和を $S$ にすることで脱出することができるようです。
実はmatcharate12君は魔法使いで、数列の要素を変更することができます。
その魔法の効能は、具体的には以下のようになります。

  • $1$ 以上 $N$ 以下の整数 $i$ を選び、数列の $i$ 番目の要素 $A_i$ を $A_i+M$ か、$A_i-M$ に変更する

  • この魔法は何回でも使うことが可能です。さらに、$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もしくは右上の雲マークをクリックしてアカウントを作成してください。