Pagini recente » Cod sursa (job #995322) | Cod sursa (job #913758) | Cod sursa (job #2231463) | Cod sursa (job #1984383) | Cod sursa (job #887199)
Cod sursa(job #887199)
#include <iostream>
#include <fstream>
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;
return 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();
mergesort(0,n-1);
v[n]=11111111;
out<<solve();
return 0;
}