B. Carries

Time Limit: 1000ms

Memory Limit: 65536KB

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

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

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

∑1≤i<=j≤n h(ai,aj)

Input

The input consists of multiple tests. For each test:

The first line contains 1 integer n (2≤n≤105). The second line contains n integers a1,a2,…,an. (0≤ai≤109).

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

将其对10,100,1000……进行取余的结果进行排序,如果两个数的和大于他们的取余数,则有进位

#include <bits/stdc++.h>

#define LL long long

#define fread() freopen("in.in","r",stdin)

#define fwrite() freopen("out.out","w",stdout)

using namespace std;

const int Max = 1e5+100;

int a[Max];

int b[Max];

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        for(int i=0;i<n;i++)

        {

            scanf("%d",&a[i]);

        }

        int ans=1;

        LL num=0;

        for(int i=1;i<=9;i++)

        {

            ans*=10;

            for(int k=0;k<n;k++)

            b[k]=a[k]%ans;

            sort(b,b+n);

            int j=0;

            for(int k=n-1;k>=0;k--)

            {

                for(;j<n;j++)

                {

                    if(b[k]+b[j]>=ans)

                    {

                        break;

                    }

                }

                if(j<=k)

                {

                    num--;

                }

                num+=(n-j);

            }

        }

        printf("%lld\n",num/2);

    }

    return 0;

}