Cod sursa(job #467612)

Utilizator udrescu_cristiUdrescu Cristian udrescu_cristi Data 29 iunie 2010 17:33:36
Problema Numarare triunghiuri Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<iostream.h>
#include<stdio.h>
#include<algorithm>

using namespace std;

 int st[1000],a[1000],n,i,nr=0,j,aux;

  int sol(int k)
{
 int t=1;
if(a[st[k]]+a[st[k-1]]<a[st[k-2]]) 
    t=0;
if(a[st[k]]+a[st[k-2]]<a[st[k-1]]) 
    t=0;  
if(a[st[k-1]]+a[st[k-2]]<a[st[k]]) 
    t=0;
 if(k==3&&t) return 1;
else
  return 0;
}

   void back(int k)
{
   int t=1;
 st[k]=st[k-1];
  while(st[k]<n&&k<4)
{
   st[k]++;
  for(int i=1;i<=k-1;i++)
   if(st[i]==st[k]) t=0;
 if(t) 
{ 
if(sol(k)) 
 nr++;
else
 back(k+1);
}
 }
  }
  int main()
{

 freopen("nrtri.in","r",stdin);
 freopen("nrtri.out","w",stdout);
   
   scanf("%d\n",&n);
  for(i=1;i<=n;i++)
{
 scanf("%d ",&a[i]);
   }
  
 sort(a+1,a+n+1);
 
 back(1);
 printf("%d\n",nr);
return 0;
}