← 返回题目列表

AtCoder · arc153_d

D. 数字总和

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

对于正整数 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)。找到最小可能值 \sum_{i=1}^N f(A_i + x) 其中 x 是一个非负整数。

约束

  • 1\leq N\leq 2\times 10^5
  • 1\leq A_i < 10^9

输入

输入由标准输入按以下格式给出:

N
A_1 \ldots A_N

输出

打印最小可能值 \sum_{i=1}^N f(A_i + x) 其中 x 是一个非负整数。


示例输入 1

4
4 13 8 6

示例输出 1

14

例如, x = 7 使 \sum_{i=1}^N f(A_i+x) = f(11) + f(20) + f(15) + f(13) = 14.


示例输入 2

4
123 45 678 90

示例输出 2

34

例如, x = 22 使 \sum_{i=1}^N f(A_i+x) = f(145) + f(67) + f(700) + f(112) = 34.


示例输入 3

3
1 10 100

示例输出 3

3

例如, x = 0 使 \sum_{i=1}^N f(A_i+x) = f(1) + f(10) + f(100) = 3.


示例输入 4

1
153153153

示例输出 4

1

例如, x = 9999846846847 使 \sum_{i=1}^N f(A_i+x) = f(10000000000000) = 1.