Pagini recente » Cod sursa (job #1064014) | Cod sursa (job #1882668) | Cod sursa (job #480444) | Cod sursa (job #1275077) | Cod sursa (job #1909492)
#include <fstream>
#include <iostream>
using namespace std;
void merge(int v[800], int st, int mij, int dr) {
int i = st;
int j = mij + 1;
int aux[800];
int k = 0;
while(i <= mij && j <= dr) {
if(v[i] > v[j])
aux[k++] = v[j++];
else
aux[k++] = v[i++];
}
while(i <= mij)
aux[k++] = v[i++];
while(j <= dr)
aux[k++] = v[j++];
k = 0;
for(int i = st; i <= dr; i++)
v[i] = aux[k++];
}
void interclasare(int v[800], int st, int dr) {
if(st < dr) {
int mij = st + (dr - st) / 2;
interclasare(v, st, mij);
interclasare(v, mij + 1 , dr);
merge(v, st, mij, dr);
}
}
int find_third(int v[800], int a, int b, int st, int dr) {
while(st <= dr) {
int mij = st + (dr - st) / 2;
if(v[a] + v[b] < v[mij + 1] && v[a] + v[b] >= v[mij]) {
return mij - b;
}
if(v[a] + v[b] < v[mij])
dr = mij - 1;
if(v[a] + v[b] >= v[mij])
st = mij + 1;
}
return 0;
}
int main()
{
int v[801], n;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
f >> n;
for(int i = 0; i < n; i++)
f >> v[i];
interclasare(v, 0, n - 1);
int sum = 0;
for(int a = 0; a < n - 2; a++)
for(int b = a + 1; b < n - 1; b++) {
v[n] = v[a] + v[b] + 1;
sum += find_third(v, a, b, b + 1, n - 1);
}
g << sum << endl;
return 0;
}