Cod sursa(job #589276)

Utilizator cipri20Ilinca Ciprian cipri20 Data 11 mai 2011 18:33:19
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>

FILE *in = fopen ("nrtri.in","r"), *out = fopen("nrtri.out","w");

const int maxn = 800;

int n, a[maxn];

void sortare()
{
    for (int i = 0; i < n; ++i)
        for (int j = 1; j < n; ++j)
            if (a[j] < a[j - 1])
            {
                int t = a[j];
                a[j] = a[j - 1];
                a[j - 1] = t;
            }
}

void rezolvare()
{
    int nr = 0;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
        {
            int st = j + 1, dr = n;
            int ret = j;
            while (st < dr)
            {
                int m = st + (dr - st) / 2;
                if (a[i] + a[j] >= a[m])
                {
                    st = m + 1;
                    ret = m;
                }
                else
                    dr = m;
            }

            nr = nr + ret - j;
            //printf("%d %d %d\n", i, j, ret);
        }

    fprintf(out, "%d", nr);
}

int main()
{
    fscanf(in, "%d", &n);
    for (int i = 0; i < n; ++i)
        fscanf(in, "%d", &a[i]);

    sortare();
    rezolvare();
    return 0;
}