Pagini recente » Cod sursa (job #1483596) | Cod sursa (job #1141565) | Cod sursa (job #715277) | Cod sursa (job #3239773) | Cod sursa (job #1794074)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> match;
int findLast(int index, int right, int firstPick, int secondPick) {
while (index <= right && match[index] <= match[firstPick] + match[secondPick]
&& match[firstPick] <= match[index] + match[secondPick] && match[secondPick] <= match[index] + match[firstPick]) {
index++;
}
return index - 1;
}
int binarySearch(int left, int right, int firstPick, int secondPick) {
int mid, nrSol = 0;
while (left <= right) {
mid = left + ((right - left) >> 1);
if (mid > secondPick && match[mid] <= match[firstPick] + match[secondPick]
&& match[firstPick] <= match[mid] + match[secondPick] && match[secondPick] <= match[mid] + match[firstPick]) {
mid = findLast(mid + 1, right, firstPick, secondPick);
/*for (mid; mid <= right; ++mid) {
if (match[mid] <= firstPick + secondPick && firstPick <= match[mid] + secondPick
&& secondPick <= match[mid] + firstPick)
nrSol++;
}*/
return mid;
}
else left = mid + 1;
}
return secondPick;
}
int main() {
int noOfMatches;
ifstream in("nrtri.in");
in >> noOfMatches;
// Citire vector
for (int i = 0; i < noOfMatches; ++i) {
int lenOfMatch;
in >> lenOfMatch;
match.push_back(lenOfMatch);
}
in.close();
//Sortare vector
sort(match.begin(), match.end());
int nrSol = 0;
for (int i = 0; i < noOfMatches - 1; ++i) {
for (int j = i + 1; j < noOfMatches; ++j) {
nrSol += binarySearch(0, noOfMatches - 1, i, j) - j;
}
}
ofstream out("nrtri.out");
out << nrSol << '\n';
out.close();
return 0;
}