比赛 |
noip |
评测结果 |
C |
题目名称 |
__卡片游戏 |
最终得分 |
0 |
用户昵称 |
Okami |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2016-11-04 19:06:44 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const ll maxn =500005;
ll init(){
ll x = 0;
char c = getchar();
while(c<'0'||c>'9')c = getchar();
while(c>='0'&&c<='9'){
x = x*10+c-'0';
c = getchar();
}
return x;
}
ll a[maxn],s[maxn],tmp[maxn],ans;
ll cal(int l ,int r,bool flag){
if(l>=r)return 0;
int mid = (l+r)>>1;
ll ret = cal(l,mid,flag)+cal(mid+1,r,flag);
int i = l,top = l,j = mid+1;
while(i<=mid&&j<=r){
if(s[i]+flag<=s[j])tmp[top++] = s[i++];
else{
tmp[top++] = s[j++];
ret+=mid-i+1;
}
}
while(i<=mid)tmp[top++] = s[i++];
while(j<=r)tmp[top++] = s[j++];
for(i = l;i<=r;++i)s[i] = tmp[i];
return ret;
}
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
int main(){
freopen("xgame.in","r",stdin);
freopen("xgame.out","w",stdout);
ll n,l,r;
cin>>n>>l>>r;
s[0] = 0;
for(int i = 1;i<=n;++i){
a[i] = init();
s[i] = s[i-1]+a[i]-r;
}
ans = cal(0,n,1);
s[0] = 0;
for(int i = 1;i<=n;++i){
s[i] = s[i-1]+a[i]-l;
}
ans -= cal(0,n,0);
if(ans==0)cout<<"0\n";
else{
ll limit = n*(n+1)/2;
if(ans==limit)cout<<"1\n";
else{
ll d = gcd(limit,ans);
cout<<ans/d<<'/'<<limit/d<<endl;
}
}
fclose(stdin);
fclose(stdout)
return 0;
}