Pagini recente » Cod sursa (job #14664) | Cod sursa (job #2325440) | Cod sursa (job #942389) | Cod sursa (job #174772) | Cod sursa (job #2614882)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int n, cnt;
int arr[805];
void interclasare(int st1, int dr1, int st2, int dr2){
int i = st1;
int j = st2;
int k = 0;
int * auxarr = new int[dr1 - st1 + dr2 - st2 + 5];
while(i <= dr1 && j <= dr2){
if(arr[i] <= arr[j]){
auxarr[k] = arr[i];
i += 1;
}
else{
auxarr[k] = arr[j];
j += 1;
}
k += 1;
}
while(i <= dr1){
auxarr[k] = arr[i];
i += 1;
k += 1;
}
while(j <= dr2){
auxarr[k] = arr[j];
j += 1;
k += 1;
}
for(int i = 0; i < k; i++)
arr[st1 + i] = auxarr[i];
delete[] auxarr;
}
void mergesort(int st, int dr){
if(st >= dr)
return;
int m = (st + dr) / 2;
mergesort(st, m);
mergesort(m + 1, dr);
interclasare(st, m, m + 1, dr);
}
int binarysearch(int x, int i, int j){
while(i < j){
int m = i + (j - i) / 2;
if(arr[m] <= x){
i = m + 1;
}
else{
j = m;
}
}
if(arr[(i + j) / 2] > x)
return ((i + j) / 2) - 1;
return j;
}
int main(){
f>>n;
for(int i = 0; i < n; i++)
f>>arr[i];
mergesort(0, n - 1);
for(int i = 0; i < n - 2; i++)
for(int j = i + 1; j < n - 1; j++){
int k = binarysearch(arr[i] + arr[j], j + 1, n - 1);
if(k >= 0){
cnt += k - j;
}
}
g<<cnt;
///cout<<binarysearch(25, 0, 16)<<" "<<binarysearch(30, 0, 16)<<" "<<binarysearch(41, 0, 16)<<" "<<binarysearch(60, 0, 16)<<" "<<binarysearch(68, 0, 16);
return 0;
}