Cod sursa(job #2489936)

Utilizator WilIiamperWilliam Damian Balint WilIiamper Data 9 noiembrie 2019 13:35:34
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>

using namespace std;
ifstream fin ("nrtri.in");
ofstream fout ("nrtri.out");
int n, b[1001], a[1001], nr;

void cautbin(int l, int h, int val, int pos) {
    while (l <= h) {
        int mid = l + (h-l)/2;
        if (b[mid] < val)
            l = mid+1;
        else if (b[mid] > val)
            h = mid-1;
        else {
            h = mid;
            break;
        }
    }
    while (h > pos) {
        h--;
        nr++;
    }
}

void merging(int l, int m, int h) {
    int i, j, k=1;
    for (i = l, j = m+1; i <= m && j <= h;) {
        if (b[i] < b[j])
            a[k++] = b[i++];
        else
            a[k++] = b[j++];
    }
    for (;i <= m; i++)
        a[k++] = b[i];
    for (;j <= h; j++)
        a[k++] = b[j];
    for (i = h; i >= l; i--)
        b[i] = a[--k];
}

void mergesort (int l, int h) {
    if (l < h) {
        int mid = l + (h-l)/2;
        mergesort(l, mid);
        mergesort(mid+1, h);
        merging(l, mid, h);
    }
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> b[i];
    mergesort(1, n);
    for (int i = 1; i < n; i++)
        cautbin(1, n, b[i]+b[i+1], i+1);
    fout << nr;
    return 0;
}