AtCoder Grand Contest 044
翻译中…
Problem Statement
翻译中…
You start with the number $0$ and you want to reach the number $N$.
翻译中…
You can change the number, paying a certain amount of coins, with the following operations:
翻译中…
- Multiply the number by
$2$, paying$A$coins. - Multiply the number by
$3$, paying$B$coins. - Multiply the number by
$5$, paying$C$coins. - Increase or decrease the number by
$1$, paying$D$coins.
翻译中…
You can perform these operations in arbitrary order and an arbitrary number of times.
翻译中…
What is the minimum number of coins you need to reach $N$?
翻译中…
You have to solve $T$ testcases.
翻译中…
Constraints
翻译中…
$1 \le T \le 10$$1 \le N \le 10^{18}$$1 \le A, B, C, D \le 10^9$- All numbers
$N, A, B, C, D$are integers.
翻译中…
Input
翻译中…
The input is given from Standard Input. The first line of the input is
翻译中…
T翻译中…
Then, $T$ lines follow describing the $T$ testcases. Each of the $T$ lines has the format
翻译中…
N A B C D翻译中…
Output
翻译中…
For each testcase, print the answer on Standard Output followed by a newline.
翻译中…
样例
Input #1
5
11 1 2 4 8
11 1 2 2 8
32 10 8 5 4
29384293847243 454353412 332423423 934923490 1
900000000000000000 332423423 454353412 934923490 987654321
Output #1
20
19
26
3821859835
23441258666
For the first testcase, a sequence of moves that achieves the minimum cost of $20$ is:
- Initially $x = 0$.
- Pay $8$ to increase by $1$ ($x = 1$).
- Pay $1$ to multiply by $2$ ($x = 2$).
- Pay $1$ to multiply by $2$ ($x = 4$).
- Pay $2$ to multiply by $3$ ($x = 12$).
- Pay $8$ to decrease by $1$ ($x = 11$).
For the second testcase, a sequence of moves that achieves the minimum cost of $19$ is:
- Initially $x = 0$.
- Pay $8$ to increase by $1$ ($x = 1$).
- Pay $1$ to multiply by $2$ ($x = 2$).
- Pay $2$ to multiply by $5$ ($x = 10$).
- Pay $8$ to increase by $1$ ($x = 11$).
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。