No.2039 Copy and Avoid
タグ : / 解いたユーザー数 80
作問者 :
milkcoffee
/ テスター :
nok0
riano
Problem Statement
Mentoscola-kun has integers $x,y$. Initially, $x=1, y=1$.
He wants to make $x=N$ by repeatedly choosing one of the following $2$ operations (the value of $y$ can be anything).
- Operation $a$: Replace the value of $x$ with $x+y$. This operation costs $A$ yen per $1$ use.
- Operation $b$: Replace the value of $y$ with $x$. This operation costs $B$ yen per $1$ use.
At no point may $x$ become a disliked integer.
Is it possible to make $x=N$? If it is possible, what is the minimum amount of money, in yen, needed to make $x=N$?
Input
$N$ $M$ $A$ $B$ $C_1$ $C_2$ $\cdots$ $C_M$
Output
If it is possible to make $x=N$, output as an integer the minimum amount of money Mentoscola-kun needs.
If it is impossible to make $x=N$, output -1.
Sample
Sample 1
Input
6 1 2 5 4
Output
11
Initially, $x=1,y=1$.
Perform operation $a$. This gives $x=2,y=1$ and costs $2$ yen.
Perform operation $a$. This gives $x=3,y=1$ and costs $2$ yen.
Perform operation $b$. This gives $x=3,y=3$ and costs $5$ yen.
Perform operation $a$. This gives $x=6,y=3$ and costs $2$ yen.
We were able to make $x=6$ for a total of $11$ yen. This is the minimum amount of money needed.
Performing operation $a$ $5$ times is not allowed, because $x=4$ would occur along the way.
Sample 2
Input
1000000000 5 1000000000 1000000000 2 7 3 11 10
Output
-1
It is impossible to make $x=1000000000$.
Sample 3
Input
200 19 12 60 3 18 31 46 53 60 73 77 89 100 113 114 138 144 154 159 167 185 192
Output
324
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。