cf C. Tourist Problem

http://codeforces.com/contest/340/problem/C

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 100010
 5 #define ll __int64
 6 using namespace std;
 7 
 8 ll a[maxn];
 9 int n;
10 
11 ll gcd(ll a,ll b)
12 {
13     return b==0?a:gcd(b,a%b);
14 }
15 
16 int main()
17 {
18     scanf("%d",&n);
19     ll ans=0;
20     for(int i=0; i<n; i++)
21     {
22         scanf("%I64d",&a[i]);
23         ans+=a[i];
24     }
25     sort(a,a+n);
26     for(int i=1; i<=n-1; i++)
27     {
28         ans+=(a[i]-a[i-1])*i*(n-i)*2;
29     }
30     int k=gcd(ans,n);
31     printf("%I64d %I64d
",ans/k,(ll)n/k);
32     return 0;
33 }

View Code