Cod sursa(job #2001377)

Utilizator BarbumateiBarbu Matei Barbumatei Data 16 iulie 2017 15:57:22
Problema Numarare triunghiuri Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <stdio.h>
#include <stdlib.h>
#define NMAX 2000
#define usi unsigned short int
#define este(a, b, c) (a<=b && b<=c)
usi v[NMAX], log=1, n;
  FILE *fin, *fout;

usi piv(int inf, int sup){
  usi st=inf, dr=sup, pivot=v[inf];
  while(st<dr){
    while(st<dr && pivot<=v[dr])
      dr--;
    v[st]=v[dr];
    while(st<dr && v[st]<=pivot)
      st++;
    v[dr]=v[st];
  }
  v[st]=pivot;
  return st;
}

void quick(int inf, int sup){
  int m=piv(inf, sup);
  if(m-1>inf)
    quick(inf, m-1);
  if(m+1<sup)
    quick(m+1, sup);
}

usi cautare(usi x){
  usi lg=log, i;
  for(i=0; lg>0; lg>>=1)
    if(i+lg<n && v[i+lg]<x)
       i+=lg;
  if(v[i]==x)
    i--;
  return i+1;
}

int main(){
  fin=fopen("nrtri.in", "r");
  fout=fopen("nrtri.out", "w");
  usi i, j, l, u, c=0;
  fscanf(fin, "%hu", &n);
  for(i=0; i<n; i++)
    fscanf(fin, "%hu", &v[i]);
  quick(0, n-1);
  ///avem triunghiul cu laturi a, b, c
  ///daca stim valorile a si b, a<=b
  /// b-a+1 <= c <= a+b-1
  ///cautam binar in vector aceste valori(lower si upper bound)
  ///si returnam nr de elem intre lower si upper-2(scadem pe a si b)
  while(log<n)
    log<<=1;
  for(i=0; i<n-2; i++)
    for(j=i+1; j<n-1; j++){
      u=cautare(v[i]+v[j]);
      c+=u-j-1;
    }
  fprintf(fout, "%d", c);
  fclose(fin);
  fclose(fout);
    return 0;
}