Cod sursa(job #1198102)

Utilizator MaarcellKurt Godel Maarcell Data 14 iunie 2014 15:44:47
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <stdio.h>
int N,a[805];
int search(int x, int y, int nr){
    int i = (x+y) /2;
    while ((a[i]>nr) && (x<=y)) { y = i - 1; i = (x+y)/2; }
    while ((a[i]<=nr) && (i<=N)) i++;

    return i-1;

}
int main(){
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);
    scanf("%d\n",&N);

    int i,j,h,aux,nr=0;
    for (i=1; i<=N; i++) scanf("%d",&a[i]);
    bool b=false;
    while (!b){
        b=true;
        for (i=1; i<N; i++) if (a[i]>a[i+1]){
            aux=a[i];
            a[i]=a[i+1];
            a[i+1]=aux;
            b=false;
            }
    }
    for (i=1; i<N-1; i++)
        for (j=i+1; j<N; j++){
            nr+=search(j+1,N,a[i]+a[j])-j;

        }
        printf("%d",nr);

        return 0;
}