Cod sursa(job #887203)

Utilizator krissu93FMI Tiugan Cristiana Elena krissu93 Data 23 februarie 2013 16:47:23
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int n;
int v[1020];

void get_data(){
ifstream in("nrtr.in");

 in>>n;
 for(int i=0;i<n;i++){
    in>>v[i];
 }
}
/*
void merge(int start, int mediu, int end){
    int contor1, contor2;
    int aux[end-start+2];
    int poz=0;
    for (contor1=start,contor2=mediu+1;contor1<=mediu || contor2<=end;)
    {
        if(contor1<=mediu&&contor2<=end)
            if (v[contor1]<v[contor2])
                aux[poz++]=v[contor1++];
             else
                aux[poz++]=v[contor2++];

         else
            if (contor1<=mediu) aux[poz++]=v[contor1++];
            else
                aux[poz++]=v[contor2++];
    }

    for (contor1=0;contor1<poz;contor1++)

            v[start+contor1]=aux[contor1];

}

void mergesort(int start, int end) {
    int middle=(start+end)/2;
    if (start==end) return;
    else
    {
        mergesort(start,middle);
        mergesort(middle+1,end);
        merge(start,middle,end);
    }
}*/
/*int cauta(int poz, int start, int finish)//cea mai mare pozitie pt care v[a]+v[b]>=v[med]
{
    int med=(start+finish)/2;
    while (start<=finish){
      if (poz>=v[med]&& v[med+1]>poz) return med;
     else
     if (poz>=v[med]){
        start=med+1;
        med=(start+finish)/2;
     }else{
     finish=med-1;
     med=(start+finish)/2;
     }
    }
    return -1;
    }
*/
int cauta(int poz,int start,int finish){
for (int i=n-1;i>start;i--){
    if (v[i]>=poz) return i;
}
return -1;
}



int solve(){
int nr=0;

for (int a=0;a<=n-3;a++)
    for (int b=a+1;b<=n-2;b++){
        int start=b+1;
        int final1=n ;
       int c=cauta(v[a]+v[b],start,final1);
        if (c>b){
            int aux=c-b;
            nr+=aux;
        }
    }
    return nr;
}

int main(){
ofstream out("nrtr.out");
get_data();
sort(v,v+n);
//mergesort(0,n-1);
v[n]=11111111;
out<<solve();
return 0;
}