estie プログラミングコンテスト2025 （AtCoder Regular Contest 210）
翻译中…
Problem Statement
翻译中…
There are $N$ types of coins. For $0\leq i\leq N-1$, the $(1+i)$-th type of coin has a value of $10^{i}$, and you possess $A_i$ of these coins.
翻译中…
You have decided to distribute these coins to $M$ people. However, the total value of coins distributed to each person must be equal. It is allowed to have coins that are not distributed.
翻译中…
Find the maximum possible total value of coins distributed to each person.
翻译中…
You are given $T$ test cases; solve each of them.
翻译中…
Constraints
翻译中…
$1\leq T\leq 10^5$$1\leq N\leq 2\times 10^5$$1\leq M\leq 10^9$$0\leq A_i\leq 10^9$- The sum of
$N$over all test cases is at most$2\times 10^5$. - All input values are integers.
翻译中…
Input
翻译中…
The input is given from Standard Input in the following format:
翻译中…
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T翻译中…
Each test case is given in the following format:
翻译中…
N M
A_0 A_1 \ldots A_{N-1}翻译中…
Output
翻译中…
Output the maximum possible total value of coins distributed to each person.
翻译中…
样例
Input #1
5
3 1
123 456 789
3 1000
123 456 789
2 3
6 14
2 3
11 14
30 4
15 9 2 66 23 2 4 1 1 32 4 80 9 10 47 14 8 7 3 16 2 39 77 4 4 2 38 64 1 2
Output #1
83583
0
42
50
19401302040124704218001124023
- For the first test case, if all coins are distributed to one person, the total value of coins distributed to each person is $123\times 10^0+456\times 10^1+789\times 10^2=83583$.
- For the second test case, there is no choice but to distribute $0$ coins to everyone.
- For the third test case, the total value of coins distributed to each person can be made $42$ as follows:
- To the $1$-st person, distribute $2$ coins of value $10^0$ and $4$ coins of value $10^1$.
- To the $2$-nd person, distribute $2$ coins of value $10^0$ and $4$ coins of value $10^1$.
- To the $3$-rd person, distribute $2$ coins of value $10^0$ and $4$ coins of value $10^1$.
- For the fourth test case, the total value of coins distributed to each person can be made $50$ as follows:
- To the $1$-st person, distribute $0$ coins of value $10^0$ and $5$ coins of value $10^1$.
- To the $2$-nd person, distribute $0$ coins of value $10^0$ and $5$ coins of value $10^1$.
- To the $3$-rd person, distribute $10$ coins of value $10^0$ and $4$ coins of value $10^1$.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。