Pagini recente » Cod sursa (job #1745703) | Cod sursa (job #2803750) | Cod sursa (job #1887495) | Cod sursa (job #2485972) | Cod sursa (job #445921)
Cod sursa(job #445921)
#include<fstream.h>
int n,x[801],nr,y[801];
void inter(int st,int m,int dr)
{
int k=st,i=st,j=m+1;
while(i<=m && j<=dr)
if(x[i]<=x[j])y[k++]=x[i++];
else y[k++]=x[j++];
while(i<=m)y[k++]=x[i++];
while(j<=dr)y[k++]=x[j++];
for(i=st;i<=dr;i++)x[i]=y[i];
}
void sort(int st,int dr)
{
if(st<dr)
{
int m=st+(dr-st)/2;
sort(st,m);sort(m+1,dr);
inter(st,m,dr);
}
}
int caut(int st,int dr,int z)
{
while(st<dr)
{
int m=st+(dr-st)/2;
if(z>=x[m])st=m+1;
else dr=m-1;
}
if(z>=x[st])return st;
return st-1;
}
int main()
{
ifstream f("nrtri.in");ofstream g("nrtri.out");
int i,j,s=0;
f>>n;for(i=1;i<=n;i++)f>>x[i];
sort(1,n);
for(i=1;i<=n-2;i++)
for(j=i+1;j<=n-1;j++)
{
s=caut(j+1,n,x[i]+x[j]);
if(s)nr=nr+(s-j);
}
g<<nr;
f.close();g.close();
return 0;
}