Nu aveti permisiuni pentru a descarca fisierul grader_test9.in

Cod sursa(job #411345)

Utilizator stephy_yoyoIonescu Stefania stephy_yoyo Data 4 martie 2010 20:42:52
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
# include <cstdio>
# include <algorithm>
using namespace std;

int v[801],t,i,j,s,n,minim,maxim;

int main ()
{
	freopen ("nrtri.in","r",stdin);
	freopen ("nrtri.out","w",stdout);
	scanf ("%d",&v[0]);
	for (i=1;i<=v[0];i++)
		scanf ("%d",&v[i]);
	sort (v+1,v+v[0]+1);
	v[v[0]+1]=500000;
	bool gasit;
	for (i=1;i<=(v[0]-2);i++)
		for (j=(i+1);j<=(v[0]-1);j++)
		{
			s=v[i]+v[j];
			minim=j;
			maxim=v[0];
			gasit=false;
			t=(minim+maxim)/2;
			while (v[minim]<=s && s<=v[maxim] &&!gasit)
			{
				if (v[t]==s)
					gasit=true;
				if (v[t]<s)
					minim=t+1;
				if (v[t]>s)
					maxim=t-1;
				t=(minim+maxim)/2;
			}
			if (gasit)
				n=n+t-2;
			else
				n=n+t-j-1;
		}
	printf ("%d",n);
	return 0;
}