Carries

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

Unfortunately, frog is somehow afraid of carries (进位). She defines 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≤nh(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

原题链接： http://acm.scu.edu.cn/soj/problem.action?id=4437

题意：给出几组测试数据，要求分别输出每组数的所有元素相加会发生多少次进位，输出进位数。

方法：分别求每位上的的进位数，直接快速排序，然后两个指针扫描。

代码如下：


#include<iostream>
#include<algorithm>
#include<cmath>
#define maxn 100005
using namespace std;
long long int mergesort(int a[],int begin,int end)
 {
     int b[maxn];
     long long num;
     long long count=0;
     int n=end+1,p;
     int q,r;
     for(int k=1;;k++)
     {
         p=0,q=0,r=end;
         num=pow(10,k);
         for(int i=0;i<n;i++)
         {
             b[i]=a[i]%num;
             if(b[i]!=a[i])
             {
                 p=1;
             }
         }
         sort(b,b+n);
         while(r!=q)
         {
             if(b[q]+b[r]>=num)
             {
                 count+=r-q;
                 r--;
             }
             else 
             {
                 q++;
             }
         }
         if(p==0)
         break;
     }
     return count;
 }
int main(void)
 {
     int n,a[maxn];
     while(cin>>n)
     {
         for(int i=0;i<n;i++)
         cin>>a[i];
         cout<<mergesort(a,0,n-1)<<endl;
     }
     return 0;
 }

巴特西

2015四川省acm B题

Carries

Input

Output

Sample Input

Sample Output

最新文章

热门文章