No.2039 Copy and Avoid
タグ : / 解いたユーザー数 71
作問者 :
milkcoffee
/ テスター :
nok0
riano
問題文
メントスコーラ君は整数 $x,y$ を持っています。最初 $x=1, y=1$ です。
メントスコーラ君は以下の $2$ つの操作のどちらかを選ぶことを繰り返し、 $x=N$ としたいです ( $y$ の値はなんでも良いです) 。
- 操作 $a$ : $x$ の値を $x+y$ で置き換える。この操作 $1$ 回につき $A$ 円かかる。
- 操作 $b$ : $y$ の値を $x$ で置き換える。この操作 $1$ 回につき $B$ 円かかる。
途中で $x$ が嫌いな整数になってはいけません。
$x=N$ とすることはできますか。できるとき、$x=N$ にするために必要な金額は最小で何円ですか。
入力
$N$ $M$ $A$ $B$ $C_1$ $C_2$ $\cdots$ $C_M$
出力
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。