Cod sursa(job #97330)

Utilizator vladbBogolin Vlad vladb Data 6 noiembrie 2007 16:32:30
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include<fstream>

using namespace std;

int n,a[800],c;

int dei(int x,int y,int k)
{  if(x>y) return 0;
   else {  int m=(x+y)/2;
	   if(a[m]<=k&&a[m+1]>k) return m;
	   else if(a[m]>k) return dei(x,m-1,k);
		else return dei(m+1,y,k);
	}
}

int main()
{  int i,j,k,cont,aux;
   ifstream fin("nrtri.in");
   ofstream fout("nrtri.out");
   fin>>n;
   for(i=1;i<=n;i++)
           fin>>a[i];
   do{ cont=0;
       for(i=1;i<n;i++)
       if(a[i]>a[i+1]){ aux=a[i];
                        a[i]=a[i+1];
                        a[i+1]=aux;
                        cont=1;
                      }
       }while(cont);   
   for(i=1;i<n;i++)
      for(j=i+1;j<n;j++)
        c+=j-dei(1,n,a[i]+a[j]);
   fout<<c;
   fin.close();
   fout.close();
   return 0;
}