Cod sursa(job #1233458)

Utilizator A63N7pTudor Nazarie A63N7p Data 25 septembrie 2014 15:04:54
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>
using namespace std;

int a[805];
int N;

int search(int, int, int);

int main()
{
    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);

    scanf("%d", &N);

    int i, j, aux, nr = 0;

    for (i = 1; i <= N; i++) scanf("%d", &a[i]);

    bool b = false;

    while (!b) {
        b = true;

        for (i = 1; i < N; i++) if (a[i] > a[i+1]) {
                aux = a[i];
                a[i] = a[i+1];
                a[i+1] = aux;
                b = false;
            }
    }

    for (i = 1; i < N - 1; i++)
        for (j = i + 1; j < N; j++) {
            nr += search(j + 1, N, a[i] + a[j]) - j;

        }

    printf("%d", nr);

    return 0;
}

int search(int x, int y, int nr)
{
    int i = (x + y) / 2;

    while ((a[i] > nr) && (x <= y)) {
        y = i - 1;
        i = (x + y) / 2;
    }

    while ((a[i] <= nr) && (i <= N)) i++;

    return i - 1;

}