Cod sursa(job #990985)

Utilizator yololy97Olaru Bogdan-Ioan yololy97 Data 29 august 2013 13:32:12
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
// fac eu sortarea
#include <cstdio>
#include <algorithm>

using namespace std;

int a[801];
int n;
int result;

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

void solve() {
    sort(a + 1, a + n + 1);

    int i, j, k;
    // continua tu
    for(i = 1; i <= n; ++i)
        for(j = i + 1; j <= n; ++j) {
            // cauti binar pe k
            int left = i + 1, right = n, middle;
            while (left <= right) {
                //printf ("%d %d\n", left, right);
                middle = (left + right) / 2;
                if (left + 1 == right) {
                    if (a[i] + a[j] >= a[right])
                        middle = right;
                    else
                        middle = left;
                    break;
                }
                if (left == right) {
                    middle = left;
                    break;
                }
                if (a[i] + a[j] >= a[middle]) // respecta conditia
                    left = middle; // ne ducem in dreapta
                else
                    right = middle - 1;
            }
            if (a[i] + a[j] >= a[middle])
                result += middle - j;//?da, dar nu aici e problema
            // el ruleaza la infinit in while       
        }
        

}//bun?da

int main() {
    read();
    solve();
    freopen("nrtri.out","w",stdout);
    printf("%d ",result);
}