Pagini recente » Cod sursa (job #2079360) | Cod sursa (job #2484685) | Cod sursa (job #798975) | Cod sursa (job #2275673) | Cod sursa (job #983437)
Cod sursa(job #983437)
#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
#include <climits>
using namespace std;
ifstream fin ("nrtri.in");
ofstream fout("nrtri.out");
#define MAX 32768
int n,A,B,a[MAX],i,j,b[MAX];
int BS(int start, int end, int x)
{
int mid;
if(a[end]<=x)
return end;
if(a[start]>x)
return start-1;
while(start<=end)
{
mid=start+(end-start)/2;
if(a[mid]<x && x<a[mid+1])
{
return mid;
}
else if(a[mid]==x && a[mid+1]!=x)
{
return mid;
}
else if(a[mid]==x)
{
start=mid+1;
}
else if(x<a[mid])
{
end=mid-1;
}
else
{
start=mid+1;
}
}
return start-1;
}
void sort()
{
int ok,k=0;
do
{
ok=1;
for(i=1;i<n-k;i++)
{
if(a[i]>a[i+1])
{
int t=a[i];
a[i]=a[i+1];
a[i+1]=t;
ok=0;
}
}
k++;
}while(!ok);
}
int main()
{
fin>>n;
for(i=1;i<=n;i++)
{
fin>>a[i];
}
sort();
int count=0;
for(i=1;i<n-1;i++)
{
for(j=i+1;j<n && a[i]+a[j]>=a[j+1];j++)
{
count+=BS(j,n,a[i]+a[j])-j;
}
}
fout<<count;
return 0;
}
/*
#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
#include <climits>
using namespace std;
ifstream fin ("teams.in");
ofstream fout("teams.out");
#define MAX 32768
int n,A,B,a[MAX],i,j,b[MAX];
int BS(int start, int end, int x)
{
int mid;
if(a[end]<=x)
return end;
if(a[start]>x)
return start-1;
while(start<=end)
{
mid=start+(end-start)/2;
if(a[mid]<x && x<a[mid+1])
{
return mid;
}
else if(a[mid]==x && a[mid+1]!=x)
{
return mid;
}
else if(a[mid]==x)
{
start=mid+1;
}
else if(x<a[mid])
{
end=mid-1;
}
else
{
start=mid+1;
}
}
return start-1;
}
void loop()
{
int k=0;
for(i=0; i<=MAX && k<=n; i++)
{
while(b[i]>0)
{
k++;
a[k]=i;
b[i]--;
}
}
cout<<INT_MAX;
}
int main()
{
fin>>n>>A>>B;
a[0]=INT_MIN;
a[n+1]=INT_MAX;
for(i=1;i<=n;i++)
{
fin>>j;
b[j]++;
}
loop();
int count=0;
for(i=1;i<=n;i++)
{
count=count+(BS(i+1,n,B-a[i])-BS(i+1,n,A-i-1));
// cout<<BS(i+1,n,B-a[i])<<"-"<<BS(i+1,n,A-i-1)<<"="<<(BS(i+1,n,B-a[i])-BS(i+1,n,A-i-1))<<"\n";
if((a[i]+a[i+1])>B)
break;
}
fout<<count;
// cout<<count;
}
*/