Cod sursa(job #588188)

Utilizator balakraz94abcd efgh balakraz94 Data 7 mai 2011 10:49:14
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<cstdio>
#include<algorithm>
#define nmax 805
using namespace std;

int P,n,nr;
int a[nmax];

void citeste();
void rezolva();
void afiseaza(long);

void citeste()
{
	freopen("nrtri.in","r",stdin);
	
	scanf("%d",&n);
	
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	
	fclose(stdin);
}



void rezolva()
{

	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
		{
	        int u=a[i]+a[j];
			
			if(u>=a[n]) nr+=n-j;
			else
			{
				int st,dr,mij;
				st=j+1;
				dr=n;
				
				while(st<dr)
				{
					mij=(st+dr)/2;
					if(a[mij]<u) st=mij+1;
					else dr=mij-1;
				}
				nr+=dr-j-1;
			}
		}
}


void afiseaza()
{
	freopen("nrtri.out","w",stdout);
	
	printf("%d\n",nr);
	
	fclose(stdout);
}

int main()
{
	citeste();
	
	sort(a+1,a+n+1);
	
	rezolva();
	
	afiseaza();
}