Cod sursa(job #2034401)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 7 octombrie 2017 19:24:01
Problema Numarare triunghiuri Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int n, v[801], cnt;
int pas, indice1, nr_format1, indice2, nr_format2;


// cu cautare binara
// 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) - 1;
//       nr_format1 = 0;
//       nr_format2 = 0;

//       for (pas; pas > 0; pas = pas >> 1){
//       	indice1 = nr_format1 + pas;
//       	indice2 = nr_format2 + pas;

//       	if (indice1 <= n && v[indice1] <= v[i] + v[j] && v[i] <= v[indice1] + v[j] && v[j] <= v[indice1] + v[i])
//       		nr_format1 += pas;
//         if (indice2 <= n && (v[indice2] > v[i] + v[j] || v[i] > v[indice2] + v[j] || v[j] > v[indice2] + v[j]))
//           nr_format2 += pas;
//       }

//       if (nr_format1 <= j)
//       	continue;
//       else{
//       	if (nr_format2 > nr_format1)
//           cnt += nr_format1 - j;
//         else{
//           if (nr_format2 <= j)
//             cnt += nr_format1 - j;
//           else
//             cnt += nr_format1 - nr_format2 + 1;
//         }
//       }

// 		}
// 	}

// 	out << cnt;

// 	return 0;
// }


// 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;
}