問題一覧 > 通常問題

No.2039 Copy and Avoid

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

問題文

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

  • 操作 $a$ : $x$ の値を $x+y$ で置き換える。この操作 $1$ 回につき $A$ 円かかる。
  • 操作 $b$ : $y$ の値を $x$ で置き換える。この操作 $1$ 回につき $B$ 円かかる。
また、メントスコーラ君は $M$ 個の嫌いな整数があります。 $i$ 番目の嫌いな整数は $C_i$ です。
途中で $x$ が嫌いな整数になってはいけません。

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

入力

$N$ $M$ $A$ $B$
$C_1$ $C_2$ $\cdots$ $C_M$

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

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

    サンプル

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

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

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

    $x=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もしくは右上の雲マークをクリックしてアカウントを作成してください。