题目地址：http://acm.scu.edu.cn/soj/problem.action?id=4437

Carries

frog has nn integers a1,a2,…,ana1,a2,…,an, and she wants to add them pairwise.

Unfortunately, frog is somehow afraid of carries (进位). She defines hardness h(x,y)h(x,y)for adding xx and yy the number of carries involved in the calculation. For example, h(1,9)=1,h(1,99)=2h(1,9)=1,h(1,99)=2.

Find the total hardness adding nn integers pairwise. In another word, find

∑1≤i<j≤nh(ai,aj)∑1≤i<j≤nh(ai,aj)

.

Input

The input consists of multiple tests. For each test:

The first line contains 11 integer nn (2≤n≤1052≤n≤105). The second line contains nnintegers a1,a2,…,ana1,a2,…,an. (0≤ai≤1090≤ai≤109).

Output

For each test, write 11 integer which denotes the total hardness.

Sample Input

    25 5100 1 2 3 4 5 6 7 8 9

Sample Output

    120

---

 首先就是一个转化，分别对10， 100,   ..... 1e9 取余， 然后按照余数排序，

两两之间相加如果大于当前的取余的数（10，1e9），就有进位

用二分搜索就可以过了

#include<bits/stdc++.h>
using namespace std;
using lon = long long;const int M = 1e5 + 5;
int a[M], b[M];int main()
{int n;while(cin >> n){for(int i = 0; i < n; i++)scanf("%d", a+i);lon ans = 0, num = 1;for(int i = 1; i <= 9; i++){num *= 10;for(int k = 0; k < n; k++)b[k] = a[k] % num;sort(b, b+n);for(int k = 0; k < n; k++){int id = lower_bound(b+k+1, b+n, num - b[k]) - b;ans += n - id;}}cout << ans << endl;}return 0;
}