Cod sursa(job #2154364)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 6 martie 2018 21:39:51
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda sim02 Marime 1.49 kb
#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;
}