Cod sursa(job #3296144)

Utilizator razviii237Uzum Razvan razviii237 Data 11 mai 2025 19:24:32
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
//#include <iostream>
#include <algorithm>
#include <fstream>
#include <algorithm>

using namespace std;
ifstream cin("nrtri.in");
ofstream cout("nrtri.out");
int v[1000], n;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> v[i];
    sort(v+1, v+n+1);
    int raspuns = 0;
    for(int i = 1; i <= n; i ++) {
        int a = v[i];
        for(int j = i+1; j <= n; j ++) {
            int b = v[j];
            int st = 1, dr = n, mij, cautare = 1;
            while(st < dr) {
                mij = (st + dr) / 2;
                if(v[mij] <= a + b)
                {st = mij + 1; cautare = mij;}
                else
                    dr = mij - 1;
            }
            if(cautare >= 3)
                raspuns += cautare - 2;
        }
    }
    cout << raspuns / 3;
    return 0;
}
// f(L) = cati araci obtinem cu lungimea L
// cel mai mare L astfel incat
// f(L) >= A

// st = 1, dr = 30000
// => mij = 1
// cautare
//while(st < dr) {
//    mij = (st + dr) / 2;
//    if(f(mij) >= A)
//        {
//          cautare = mij;
//          st = mij + 1;
//        }
//    else
//        dr = mij - 1;
//}


// a < b < c
// a + b ≥ c

// 1 2 3 4 5 6 7 8 9
// a = 3, b = 4
// a + b = 7
// c = 1...7

// 1. Sortam vectorul
// 2. for a
//       for b
//          cautam binar valoarea maxima a lui c