Cod sursa(job #339628)

Utilizator sigridMaria Stanciu sigrid Data 10 august 2009 18:02:06
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<stdio.h>
#define dim 30002

int v[dim], z[dim];

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