Pagini recente » Cod sursa (job #1677064) | Cod sursa (job #2357125) | Cod sursa (job #1573606) | Cod sursa (job #1811113) | Cod sursa (job #887114)
Cod sursa(job #887114)
#include <iostream>
#include <fstream>
using namespace std;
int n;
int v[900];
void get_data(){
ifstream in("nrtr.in");
in>>n;
for(int i=0;i<n;i++){
in>>v[i];
}
}
void Merge(int start,int med,int end1)
{
int i,j;
int Aux[end1-start+2],poz = 0;
for(i=start,j=med+1;i<=med||j<=end1;)
{
if(i<=med&&j<=end1)
if(v[i]<=v[j])
Aux[poz++] = v[i++];
else Aux[poz++] = v[j++];
else
if(i<=med)
Aux[poz++] = v[i++];
else
Aux[poz++] = v[j++];
}
for(i=0;i<poz;i++)
v[start+i] = Aux[i];
}
void MergeSort(int start,int end1)
{
int med = (start + end1)/2;
if(start==end1)
return;
else
{
MergeSort(start,med);
MergeSort(med+1,end1);
Merge(start,med,end1);
}
}
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 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-1 ;
int c=cauta(v[a]+v[b],start,final1);
if (c>b)
nr+=c-b;
}
return nr;
}
int main(){
ofstream out("nrtr.out");
get_data();
MergeSort(0,n-1);
v[n]=11111111;
out<<solve();
return 0;
}