問題一覧 > 通常問題

No.1940 Escape through + -

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

問題文

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

  • 11 以上 NN 以下の整数 ii を選び、数列の ii 番目の要素 AiA_i を Ai+MA_i+M か、Ai−MA_i-M に変更する

    • この魔法は何回でも使うことが可能です。さらに、11 つの要素に対して好きなだけ魔法をかけることができます。
    また MM はmatcharate12君によって既に定められています。

    何回も同じ魔法を使うのは大変です。なのでそれで脱出できなかったら無駄な努力です。
    与えられる数列に対して、matcharate12君は部屋から脱出することが可能かどうか判定してください。

    入力

    N M SN\ M\ S
A1 A2 … ANA_1\ A_2\ \dots \ A_N

    ・1≤N≤1051\le N\le 10^5
    ・1≤M≤10181\le M\le 10^{18}
    ・1≤S≤10181\le S\le 10^{18}
    ・1≤Ai≤1091\le A_i\le 10^9
    ・入力はすべて整数

    出力

    脱出することができるなら Yes 、できないなら No を出力してください。

    サンプル

    サンプル1
    入力
    4 2 10
1 1 1 1
    出力
    Yes

    例えば A1,A2,A3A_1,A_2,A_3 に対して、Ai+MA_i+M に変える魔法を 11 回ずつかけると、魔法をかけた後の数列は A=(1+2,1+2,1+2,1)=(3,3,3,1)A=(1+2,1+2,1+2,1)=(3,3,3,1) になります。これは総和が 1010 と等しいので、matcharate12君は脱出することが可能です。よって Yes を出力します。

    サンプル2
    入力
    2 2 5
1 3
    出力
    No

    どう魔法をかけようと総和を 55 にすることはできません。

    サンプル3
    入力
    3 1 1000000007
1 2 5
    出力
    Yes

    魔法を使用する回数が 10910^9 回を超えることがあります。

    サンプル4
    入力
    10 1414 1814
14 14 21 35 62 37 30 95 4 88
    出力
    Yes

    入力例には挙げませんが、魔法を使用した後の数列の要素が 101810^{18} を超えることがあることに注意してください。

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。