Cod sursa(job #372154)

Utilizator blasterzMircea Dima blasterz Data 8 decembrie 2009 23:16:50
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <cstdio>
#include <algorithm>
#define N 801

using namespace std;

int a[N], n;

void read()
{
    freopen("nrtri.in","r",stdin);
    scanf("%d\n", &n);
    for(int i = 1; i <= n; ++i)
	scanf("%d ", &a[i]);

    sort(a+1, a+n+1);
}

void solve()
{
    int i, j, k, cnt;
    int sol = 0;

    /*
    for(i = 1; i <= n; ++i)
	printf("%d ", a[i]);
    printf("\n");
*/
    for(i = 1; i < n - 1; ++i)
	for(j = i + 1; j < n; ++j)
	{
	    int v = a[i] + a[j];
	    //caut binar a[k] >= v
	    for(k = j + 1, cnt = (1<<10); cnt; cnt >>= 1)
		if(k + cnt <= n)
		    if(a[k + cnt] <= v) 
			k += cnt;
   
	     
//	    printf("%d %d %d\n",i, j, k);
	    sol += k - j;
	    if(a[k] > v) --sol;
	}

    freopen("nrtri.out","w",stdout);
    printf("%d\n", sol);
}

int main()
{
    read();
    solve();
    return 0;
}