102574: [AtCoder]ABC257 E - Addition and Multiplication 2
Description
Score : $500$ points
Problem Statement
Takahashi has an integer $x$. Initially, $x=0$.
Takahashi may do the following operation any number of times.
- Choose an integer $i\ (1\leq i \leq 9)$. Pay $C_i$ yen (the currency in Japan) to replace $x$ with $10x + i$.
Takahashi has a budget of $N$ yen. Find the maximum possible value of the final $x$ resulting from operations without exceeding the budget.
Constraints
- $1 \leq N \leq 10^6$
- $1 \leq C_i \leq N$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $C_1$ $C_2$ $\ldots$ $C_9$
Output
Print the answer.
Sample Input 1
5 5 4 3 3 2 5 3 5 3
Sample Output 1
95
For example, the operations where $i = 9$ and $i=5$ in this order change $x$ as:
$0 \rightarrow 9 \rightarrow 95$.
The amount of money required for these operations is $C_9 + C_5 = 3 + 2 = 5$ yen, which does not exceed the budget. Since we can prove that we cannot make an integer greater than or equal to $96$ without exceeding the budget, the answer is $95$.
Sample Input 2
20 1 1 1 1 1 1 1 1 1
Sample Output 2
99999999999999999999
Note that the answer may not fit into a $64$-bit integer type.
Input
题意翻译
### 题目描述 ### 高桥君有一个整数 $x$ 。一开始的时候， $x=0$ 。 高桥君可以无限执行以下操作： - 选择一个整数 $i$ （ $1 \leq i \leq 9$ ）。支付 $C_i$ 日元，把 $x$ 变为 $10x+i$ 。 高桥君有 $N$ 日元，问 $x$ 最大是多少？ ### 约束 ### $1 \leq N \leq 10^6$ $1 \leq C_i \leq N$ 保证 $N,C_i$ 都是整数。 ### 输入格式 ### 输入数据按以下格式给出： $N$ $C_1$ $C_2$ … $C_9$ ### 输出格式 ### 输出用不超过 $N$ 日元，最多可以使 $x$ 变为多少，并在末尾换行。 ### 样例解释 ### #### 样例1 #### 分别令 $i$ 为 $9$ 和 $5$ ， $x$ 将得到 $95$ 。一共花费 $C_9+C_5=5$ 日元，并未超过 $N$ ，符合要求。这是 $x$ 的最大值。 #### 样例2 #### 请注意，答案可能无法用 $64$ 位整数表示。Output
问题描述
高桥有一个整数$x$。最初，$x=0$。
高桥可以任意多次执行以下操作。
- 选择一个整数$i\ (1\leq i \leq 9)$。支付$C_i$日元（日本的货币）将$x$替换为$10x + i$。
高桥有一个预算$N$日元。在不超过预算的情况下，求通过操作得到的最终$x$的最大可能值。
约束
- $1 \leq N \leq 10^6$
- $1 \leq C_i \leq N$
- 输入中的所有值都是整数。
输入
从标准输入按照以下格式给出输入：
$N$ $C_1$ $C_2$ $\ldots$ $C_9$
输出
打印答案。
样例输入1
5 5 4 3 3 2 5 3 5 3
样例输出1
95
例如，按照顺序执行操作$i = 9$和$i=5$会改变$x$为：
$0 \rightarrow 9 \rightarrow 95$。
这些操作所需的费用为$C_9 + C_5 = 3 + 2 = 5$日元，不超过预算。由于我们可以在不超过预算的情况下证明无法将整数变为大于或等于$96$的数，因此答案为$95$。
样例输入2
20 1 1 1 1 1 1 1 1 1
样例输出2
99999999999999999999
请注意，答案可能无法容纳到$64$位整数类型中。