Cod sursa(job #1465181)

Utilizator theep0Cruceru Radu theep0 Data 26 iulie 2015 17:38:20
Problema Numarare triunghiuri Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <stdio.h>
#include <stdlib.h>

void _mergeSort(int arr[], int temp[], int left, int right);
void _merge(int arr[], int temp[], int left, int mid, int right);

void mergeSort(int arr[], int size) {
    int *temp = (int *) malloc (sizeof(int) * size);
    _mergeSort(arr, temp, 0, size - 1);
}

void _mergeSort(int arr[], int temp[], int left, int right) {
    int mid;
    if (left < right) {
        mid = (right + left) / 2;

        _mergeSort(arr, temp, left, mid);
        _mergeSort(arr, temp, mid + 1, right);

        _merge(arr, temp, left, mid + 1, right);
    }
}

void _merge(int arr[], int temp[], int left, int mid, int right) {
    int l = left, m = mid, k = left;

    while ((l < mid) && (m <= right)) {
        if (arr[l] <= arr[m]) {
            temp[k++] = arr[l++];
        } else {
            temp[k++] = arr[m++];
        }
    }

    while (l < mid) {
        temp[k++] = arr[l++];
    }

    while (m <= right) {
        temp[k++] = arr[m++];
    }

    for (l = left; l <= right; l++) {
        arr[l] = temp[l];
    }
}

int bs(int arr[], int left, int right, int v) {
    int m = 0; 
    int oleft = left;
    while (left < right) {
        m = (right + left) / 2;
        if (arr[m] == v) {
            break;
        }
        if (arr[m] < v) {
            left = m + 1;
        } else {
            right = m;
        }
    }
    if (arr[oleft] <= arr[m]) {
        return m + 1;
    }
    return -1;
}

int main() {
    int i, j, k, n, c, *a;
    FILE *fi, *fo;

    fi = freopen("nrtri.in", "r", stdin);
    fo = freopen("nrtri.out", "w", stdout);
    scanf("%d", &n);
    a = (int *) malloc(sizeof(int) * n);
    for (i = 0; i < n; i++) {
        scanf("%d", a + i);
    }
    mergeSort(a, n);
    c = 0;
    for (i = 0; i < n - 2; i++) {
        for (j = i + 1; j < n - 1; j++) {
            for (k = j + 1; k < n; k++) {
                if (a[i] + a[j] >= a[k]) {
                    c++;
                } else {
                    break;
                }
            }
        }
    }
    printf("%d\n", c);
    fclose(fi);
    fclose(fo);

    return 0;
}