Cod sursa(job #1355432)

Utilizator Alex1199Alex Bercea Alex1199 Data 22 februarie 2015 18:10:23
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int n, a[809], r, sol;
bool t=true;
int caut(int s, int d,int c)
{   if(s>d) {t=false; return s;}
   else
  {
    int m=(s+d)/2;
    if(a[m]==c) return m;
    else
        {
           if(a[m]<c) return caut(m+1,d,c);
                 else return caut(s,m-1,c);
        }
  }
}

int main()
{
 f>>n; for(int i=1;i<=n;i++){f>>a[i];}
 sort(a+1,a+n+1);
  for(int i=1;i<n-1;i++)
  {
      for(int j=i+1;j<n;j++)
      {
        t=true;
        r=caut(j+1,n,a[i]+a[j]);
       if(t)
        {
          while(a[r+1]==a[i]+a[j]) r++;
           sol+=r-j;
        }
        else { if(r<=n) sol+=r-j-1;
              else sol+=n-j;  }
      }
  }
  g<<sol;
    return 0;
}