SCU - 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

$\sum_{1 \leq i < j \leq n} h (a i, a j)$

Input

The input consists of multiple tests. For each test:

The first line contains 1integer $ n, 2≤n≤10^5)$. The second line contains $n$ integers a1,a2,…,ana1,a2,…,an. ( $0 \leq a i \leq 1 0^{9}$ ).

Output

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

Sample Input

    2
    5 5
    10
    0 1 2 3 4 5 6 7 8 9

Sample Output

    1
    20

题意：

第一行给出一个数N，然后下面的N个数，统计任意两个数的进位之和。
例如h(35,82) = 1,h(1,99) = h(99,1) = 2;

思路：

我们只要记录每个数字进个位的有多少个，进十位的有多少个，进百位的有多少个… 最后将统计结果相加即可。

假设我们现在求进百位的有多少个，那么就把所有数字全都取余100，假如这个数是164，算出大于等于100-64的数有多少个即可，其他进位的过程与百位相似。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll na[100010],tmp[100010];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    while(cin>>n)
    {
        for(ll i=0;i<n;++i) cin>>na[i];
        ll mod=1,ans=0;;
        for(ll k=1;k<=9;++k){
            mod*=10;
            for(ll i=0;i<n;++i) tmp[i]=na[i]%mod;
            sort(tmp,tmp+n);
            for(ll i=0;i<n;++i){
                ll th=lower_bound(tmp+i+1,tmp+n,mod-tmp[i])-tmp;
                ans+=n-th;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}