[ARC153D] Sum of Sum of Digits
题意翻译
定义 $f(x)$ 为其十进制意义下各位数字之和,比如 $f(1)=1,f(123)=6$。
给定长度为 $n$ 的序列 $A$,请找到一个非负整数 $x$ 使得 $\sum\limits_{i=1}^nf(A_i+x)$ 最小,并输出这个最小值。
题目描述
[problemUrl]: https://atcoder.jp/contests/arc153/tasks/arc153_d
正整数 $ x $ に対し,その各桁の和を $ f(x) $ と表すことにします.例えば $ f(153)\ =\ 1\ +\ 5\ +\ 3\ =\ 9 $,$ f(2023)\ =\ 2\ +\ 0\ +\ 2\ +\ 3\ =\ 7 $,$ f(1)\ =\ 1 $ です.
正整数列 $ A\ =\ (A_1,\ \ldots,\ A_N) $ が与えられます.$ x $ を非負整数とするとき,$ \sum_{i=1}^N\ f(A_i\ +\ x) $ としてありうる最小値を求めてください.
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられます.
> $ N $ $ A_1 $ $ \ldots $ $ A_N $
输出格式
$ x $ を非負整数とするとき,$ \sum_{i=1}^N\ f(A_i\ +\ x) $ としてありうる最小値を出力してください.
输入输出样例
输入样例 #1
4
4 13 8 6
输出样例 #1
14
输入样例 #2
4
123 45 678 90
输出样例 #2
34
输入样例 #3
3
1 10 100
输出样例 #3
3
输入样例 #4
1
153153153
输出样例 #4
1
说明
### 制約
- $ 1\leq\ N\leq\ 2\times\ 10^5 $
- $ 1\leq\ A_i\ <\ 10^9 $
### Sample Explanation 1
例えば $ x\ =\ 7 $ とすると,$ \sum_{i=1}^N\ f(A_i+x)\ =\ f(11)\ +\ f(20)\ +\ f(15)\ +\ f(13)\ =\ 14 $ となります.
### Sample Explanation 2
例えば $ x\ =\ 22 $ とすると,$ \sum_{i=1}^N\ f(A_i+x)\ =\ f(145)\ +\ f(67)\ +\ f(700)\ +\ f(112)\ =\ 34 $ となります.
### Sample Explanation 3
例えば $ x\ =\ 0 $ とすると,$ \sum_{i=1}^N\ f(A_i+x)\ =\ f(1)\ +\ f(10)\ +\ f(100)\ =\ 3 $ となります.
### Sample Explanation 4
例えば $ x\ =\ 9999846846847 $ とすると,$ \sum_{i=1}^N\ f(A_i+x)\ =\ f(10000000000000)\ =\ 1 $ となります.