Cod sursa(job #50706)

Utilizator alecmanAchim Ioan Alexandru alecman Data 8 aprilie 2007 14:29:20
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
/*
 *
 *
  infoarena 2.0 - Arhiva - Numarare Triunghiuri
 *
 *
 */

#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>

using namespace std;

#define INPUT "nrtri.in"
#define OUTPUT "nrtri.out"

FILE *fin=fopen(INPUT, "r"),*fout=fopen(OUTPUT, "w");

int n;
vector<int> a;

void citire();
void rezolvare();
int cauta(int, int);

int main()
{
  a.push_back(0);
  citire();
  sort(a.begin(),a.end());
  rezolvare();
  fclose(fin);
  fclose(fout);
  return 0;
}

void citire()
{
  int x;
  fscanf(fin, "%d", &n);
  for(int i=1;i<=n;++i)
  {
    fscanf(fin, "%d", &x);
    a.push_back(x);
  }
}

void rezolvare()
{
  int poz;
  long total=0;
  for(int i=1;i<=n;++i)
    for(int j=i+1;j<=n;++j)
    {
      poz=cauta(i,j);
      total+=(poz-j);
    }
  fprintf(fout, "%ld\n", total);
}

int cauta(int st, int dr)
{
  int pozinc,pozsf,pozmij;
  pozinc=1;
  pozsf=n;
  pozmij=(pozinc+pozsf+1)/2;
  while(pozinc<pozsf)
  {
    if(a[st]+a[dr]<a[pozmij])
    {
      pozsf=pozmij-1;
      pozmij=(pozinc+pozsf+1)/2;
    }
    else
    {
      pozinc=pozmij;
      pozmij=(pozinc+pozsf+1)/2;
    }
  }
  return pozmij;
}