Cod sursa(job #327553)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 29 iunie 2009 12:47:51
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<stdio.h>

int a[810],f[60001],max,i,j,n,rez,k;

int cautbin( int x)
{ int st=1,dr=n,mij;
  while(st<=dr) { mij=(st+dr)/2;
                  if((a[mij]<=x&&a[mij+1]>x)||(a[mij]<=x&&mij+1==n)) return mij;
                  else if(a[mij]<=x&&a[mij+1]<=x) st=mij+1;
                  else dr=mij-1;
                }
  return 0;
}                


int main()
{ 
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);
    
    scanf("%d",&n);
    
    for(i=1;i<=n;i++) {  scanf("%d",&a[i]);
                         f[a[i]]++;
                         if(a[i]>max)max=a[i];
                      }
    for(i=1;i<=max;i++)  { j=f[i];
                               while(j) { a[++rez]=i;
                                           --j;
                                        }   
                                        
                         }                    
                          
    rez=0;
    for(i=1;i<=n-2;i++)
        for(j=i+1;j<=n-1;j++) { if(a[i]+a[j]>=max) rez+=n-j;
                                else { k=cautbin(a[i]+a[j]);
                                       rez+=k-j;
                                     } 
                              }         
        
        
    printf("%d\n",rez);
    fclose(stdin);
    fclose(stdout);
    return 0;
}