Cod sursa(job #2034494)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 7 octombrie 2017 21:59:54
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("nrtri.in");
ofstream out("nrtri.out");

int n, v[801], cnt;
int pas, indice, nr_format;

// brute

// int main(){
//   in >> n;

//   for (int i = 1; i <= n; ++ i)
//     in >> v[i];

//   sort(v, v + n + 1);

//   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 (v[i] + v[j] >= v[k] && v[i] + v[k] >= v[j] && v[j] + v[k] >= v[i]){
//           cnt += 1;
//           out << i << " " << j << " " << k << " " << '\n';
//         }
//       }
//     }
//   }


//   out << cnt;

//   return 0;
// }

int main(){
  in >> n;
  for (int i = 1; i <= n; ++ i)
    in >> v[i];

  sort(v, v + n + 1);

  for (int i = 1; i <= n - 2; ++ i){
    for (int j = i + 1; j <= n - 1; ++ j){
      pas = 1;
      pas = pas << 32 - __builtin_clz(n - j) - 1;

      nr_format = j;

      while (pas > 0){
        indice = nr_format + pas;

        if (indice <= n && v[indice] + v[i] >= v[j] && v[i] + v[j] >= v[indice] && v[indice] + v[j] >= v[i])
          nr_format += pas;

        pas = pas >> 1;
      }

      cnt += nr_format - j;
    }
  }

  out << cnt;

  return 0;
}