Pagini recente » Cod sursa (job #2817524) | Cod sursa (job #2065475) | Cod sursa (job #2676960) | Cod sursa (job #1278657) | Cod sursa (job #2490036)
#include <fstream>
using namespace std;
ifstream fin ("nrtri.in");
ofstream fout ("nrtri.out");
int n, b[1001], a[1001], nr;
void cautbin(int l, int h, int val, int pos) {
while (l <= h) {
int mid = l + (h-l)/2;
if (b[mid] < val)
l = mid+1;
else if (b[mid] > val)
h = mid-1;
else {
h = mid;
break;
}
}
while (h > pos) {
h--;
nr++;
}
}
void merging(int l, int m, int h) {
int i, j, k=1;
for (i = l, j = m+1; i <= m && j <= h;) {
if (b[i] < b[j])
a[k++] = b[i++];
else
a[k++] = b[j++];
}
for (;i <= m; i++)
a[k++] = b[i];
for (;j <= h; j++)
a[k++] = b[j];
for (i = h; i >= l; i--)
b[i] = a[--k];
}
void mergesort (int l, int h) {
if (l < h) {
int mid = l + (h-l)/2;
mergesort(l, mid);
mergesort(mid+1, h);
merging(l, mid, h);
}
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
fin >> b[i];
mergesort(1, n);
for (int i = 1; i < n; i++)
for (int j = i+1; j <= n; j++)
cautbin(1, n, b[i]+b[j], j);
fout << nr;
return 0;
}