[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 $ となります.