Cod sursa(job #1910695)

Utilizator TzeentchIoan-Teodor Tzeentch Data 7 martie 2017 17:55:39
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <cstdio>

using namespace std;

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

void interplasare(int a[801], int st, int p, int dr){
    int c[801], k=0;
    int i=st, j=p+1;
    while(i<=p&&j<=dr){
        if(a[i]<a[j]){
            c[k++]=a[i++];
        }
        else c[k++]=a[j++];
    }
    while(i<=p){
        c[k++]=a[i++];
    }
    while(j<=dr){
        c[k++]=a[j++];
    }
    k=0;
    for(int i=st;i<=dr;i++){
        a[i]=c[k++];
    }
}

void srt(int a[801], int st, int dr){
    if(st<dr){
        int p=st+(dr-st)/2;
        srt(a, st, p);
        srt(a, p+1, dr);
        interplasare(a, st, p, dr);
    }
}

int cbin(int a[801], int x, int y, int st, int dr){
    int s=a[x]+a[y];
    while(st<=dr){
        int p=st+(dr-st)/2;
        if(a[p]<=s&&a[p+1]>s){
            return p-y;
        }
        else {
            if(a[p]>s){
                dr=p-1;
            }
            else st=p+1;
        }
    }
    return 0;
}

int main()
{
    int a[801];
    int n, i, j, s=0;
    fscanf(in, "%d", &n);
    for(i=0;i<n;i++){
        fscanf(in, "%d", &a[i]);
    }
    srt(a, 0, n-1);
    for(i=0;i<n-2;i++){
        int x=a[i];
        for(j=i+1;j<n-1;j++){
            int y=a[j];
            a[n]=x+y+1;
            s+=cbin(a, i, j, j+1, n-1);
        }
    }
    fprintf(out, "%d", s);
    return 0;
}