Cod sursa(job #1796010)

Utilizator gorneanu.andreiFMI Gorneanu Andrei gorneanu.andrei Data 3 noiembrie 2016 00:04:23
Problema Numarare triunghiuri Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <stdio.h>
#define MAX 801
int v[MAX],n;

    int pozitie(int i, int j){

    int mod = 1 , aux;

    while(i < j){

        if(v[i] > v[j]){

            aux = v[i];
            v[i] = v[j];
            v[j] = aux;
            mod = 1 - mod;
        }
        i = i + mod;
        j = j + mod -1;

    }
    return i;

    }

    void divide(int i , int j){

    int k;


    if(i < j){
        k = pozitie(i,j);
        divide(i,k-1);
        divide(k+1,j);
    }
    }

    int cautareBinara(int x,int j){

    int i , step , OK = 1;

    for(step = 1;step <= n;step <<= 1);
        for(i = 0 ;step;step >>= 1)
            if((i + step <= n) && (v[i + step] <= x))
                i = i + step;

            if(i > j)
            return i;

            return -1;
    }

int main()

{   int i,total = 0,j,x;
    FILE *f,*g;

    f=fopen("nrtri.in","r");
    g=fopen("nrtri.out","w+");

    fscanf(f,"%d",&n);

    for(i = 1;i <= n; ++i)
        fscanf(f,"%d",&v[i]);

    divide(1,n);


    for(i = 1;i <= n; ++i)
        for(j = 1; j <= n; ++j){
            {if(i < j)
            {x = cautareBinara(v[i] + v[j],j);
            if(v[x] <= v[i] + v[j] && x > 0)
            total = total + x - j;}}
}

    fprintf(g,"%d",total);



}