Cod sursa(job #1803602)

Utilizator mateilmatei lascu mateil Data 11 noiembrie 2016 17:02:54
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 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 < n){
     p*=2;
    }
    for(i = 0; i < n - 2; i++){
     for(j = i + 1; j < n - 1; j++){
        pas = p;
        nrk = k = j;
        while(v[i] + v[j] >= v[k] && pas > 0){
          if(v[k + pas] <= v[i] + v[j] && k + pas < n)
            k+=pas;
          pas = pas / 2;
        }
        s+=k-j;
     }
    }
    g<<s;
    return 0;
}