Pagini recente » Cod sursa (job #2238831) | Cod sursa (job #2447556) | Cod sursa (job #2952289) | Cod sursa (job #962038) | Cod sursa (job #2154364)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdlib>
#define MAXN 810
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int v[MAXN],n;
void cit(){
in>>n;
for(int i = 1 ; i <= n; i++)
in>>v[i];
sort(v+1,v+n+1);
}
bool ok(int i,int j,int x){
if(x <= n && v[i] + v[j] >= v[x] && v[x] + v[j] >= v[i] && v[x] + v[i] >= v[j])
return true;
return false;
}
int cautbin(int i,int j){
int pas = 1<<10,r = j;
while(pas){
if(ok(i,j,r+pas))
r += pas;
pas /= 2;
}
return r;
}
int brut(){
int cnt = 0;
for(int i = 1; i <= n-2; i ++){
for(int j = i + 1; j <= n-1; j ++){
for(int k = j + 1; k <= n; k++)
if(ok(i,j,k))
cnt++;
}
}
return cnt;
}
int rez(){
int ans = 0;
for(int i = 1; i <= n - 2; i++){
for(int j = i + 1; j <= n-1; j++){
int k = cautbin(i,j);
ans += k - j;
}
}
return ans;
}
void gen(){
n = rand()%800+1;
for(int i = 1; i <= n; i++)
v[i] = rand()%30000;
sort(v+1,v+n+1);
if(rez() != brut()){
out<<n<<"\n";
for(int i = 1; i <= n;i++)
out<<v[i]<<" ";
out<<"\n"<<rez()<<" "<<brut()<<"\n"<<"\n";
}
}
int main()
{
cit();
out<<rez();
//for(int i = 1; i <= 10000; i++)
// gen(); e bine :)
return 0;
}