Pagini recente » Cod sursa (job #2046161) | Cod sursa (job #331843) | Cod sursa (job #1846189) | template/onis-2014/footer | Cod sursa (job #1792114)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> match;
int findFirst(int index, int left, int firstPick, int secondPick) {
while (index > left && --index >= 0 && match[index] <= firstPick + secondPick
&& firstPick <= match[index] + secondPick && secondPick <= match[index] + firstPick);
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 (match[mid] <= firstPick + secondPick && firstPick <= match[mid] + secondPick && secondPick <= match[mid] + firstPick) {
mid = findFirst(mid, left, firstPick, secondPick);
for (mid; mid <= right; ++mid) {
if (match[mid] <= firstPick + secondPick && firstPick <= match[mid] + secondPick && secondPick <= match[mid] + firstPick)
nrSol++;
}
return nrSol;
}
else left = mid + 1;
}
return 0;
}
int main() {
int noOfMatches;
ifstream in("nrtri.in");
in >> noOfMatches;
for (int i = 0; i < noOfMatches; ++i) {
int lenOfMatch;
in >> lenOfMatch;
match.push_back(lenOfMatch);
}
in.close();
sort(match.begin(), match.end());
int nrSol = 0;
for (int i = 1; i < noOfMatches; ++i) {
nrSol += binarySearch(i, noOfMatches - 1, match[i], match[i - 1]);
}
ofstream out("nrtri.out");
out << nrSol << '\n';
out.close();
return 0;
}