問題一覧 > 通常問題

No.2039 Copy and Avoid

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 73
作問者 : milkcoffee / テスター : nok0 riano
7 ProblemId : 8192 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-08-09 18:17:20

問題文

メントスコーラ君は整数 x,yx,y を持っています。最初 x=1,y=1x=1, y=1 です。
メントスコーラ君は以下の 22 つの操作のどちらかを選ぶことを繰り返し、 x=Nx=N としたいです ( yy の値はなんでも良いです) 。

  • 操作 aa : xx の値を x+yx+y で置き換える。この操作 11 回につき AA 円かかる。
  • 操作 bb : yy の値を xx で置き換える。この操作 11 回につき BB 円かかる。
また、メントスコーラ君は MM 個の嫌いな整数があります。 ii 番目の嫌いな整数は CiC_i です。
途中で xx が嫌いな整数になってはいけません。

x=Nx=N とすることはできますか。できるとき、x=Nx=N にするために必要な金額は最小で何円ですか。

入力

NN MM AA BB
C1C_1 C2C_2 ⋯\cdots CMC_M

  • 3≤N≤1093 \leq N \leq 10^9
  • 1≤M≤min(N−2,5000)1 \leq M \leq \mathrm{min}(N-2,5000)
  • 1≤A,B≤1091 \leq A,B \leq 10^9
  • 2≤Ci≤N−1 (1≤i≤M)2 \leq C_i \leq N-1 \ (1 \leq i \leq M)
  • Ci≠Cj (i≠j)C_i \neq C_j \ (i \neq j)
  • 入力は全て整数である

    • 出力

    x=Nx=N とすることが可能なとき、メントスコーラ君が必要な金額の最小値を整数で出力して下さい。
    x=Nx=N とすることが不可能なとき、 -1 を出力してください。

    サンプル

    サンプル1
    入力
    6 1 2 5
4
    出力
    11

    最初 x=1,y=1x=1,y=1 です。
    操作 aa を行います。 x=2,y=1x=2,y=1 になり、 22 円かかります。
    操作 aa を行います。 x=3,y=1x=3,y=1 になり、 22 円かかります。
    操作 bb を行います。 x=3,y=3x=3,y=3 になり、 55 円かかります。
    操作 aa を行います。 x=6,y=3x=6,y=3 になり、 22 円かかります。
    合計 1111 円で x=6x=6 とすることができました。これが必要な金額の最小値です。
    操作 aa を 55 回行う方法だと、途中で x=4x=4 となってしまうため、そのような操作はできません。

    サンプル2
    入力
    1000000000 5 1000000000 1000000000
2 7 3 11 10
    出力
    -1

    x=1000000000x=1000000000 とすることができません。

    サンプル3
    入力
    200 19 12 60
3 18 31 46 53 60 73 77 89 100 113 114 138 144 154 159 167 185 192
    出力
    324

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