Cod sursa(job #1909492)

Utilizator geek_geekGeek Geek geek_geek Data 7 martie 2017 12:54:12
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#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;
}