Cod sursa(job #1803280)

Utilizator mateilmatei lascu mateil Data 11 noiembrie 2016 10:55:03
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
#include<iostream>
using namespace std;
int v[800];
int main()
{
    ifstream f("nrtri.in");
    ofstream g("nrtri.out");
    int n,i,j, aux , p , pas, s = 0 , k ,nrk;
    f>>n;
    i = 0;
    f>>v[i];
    for(i = 1; i < n; i++){
       f>>v[i];
       j = i;
       while(j > 0 && v[j] < v[j - 1]){
        aux = v[j];
        v[j] = v[j - 1];
        v[j - 1] = aux;
        j--;
       }
    }
    p = 1;
    while(p * 2 < n){
     p*=2;
    }
    for(i = 0; i < n - 2; i++){
     for(j = i + 1; j < n - 1; j++){
        pas = p;
        nrk = k = j + 1;
        while(k + pas >= n){
         pas = pas/2;
        }
        while(v[i] + v[j] >= v[k] && pas > 0){
          if(v[k + pas] <= v[i] + v[j])
            k+=pas;
          pas = pas / 2;
        }
         if(nrk != k || v[i] + v[j] >= v[k])
          s+=k - j;
     }
    }
    g<<s;
    return 0;
}