Cod sursa(job #1456067)

Utilizator MirunaBMiruna Budoias MirunaB Data 29 iunie 2015 18:51:58
Problema Numarare triunghiuri Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int n,a[100],r,s;
long int k=0;
void citire()
{
    f>>n;
    for(int i=1;i<=n;i++)
    f>>a[i];
}

void quicksort(int x,int y)
{
    if(x<y)
    {
        int i=x,j=y,p=a[x];
        while(i<j)
        {
            if(a[i]>a[j])
            {
                int h=a[i];
                a[i]=a[j];
                a[j] =h;
            }
            if(p==a[i])
                j--;
            else
                i++;
        }
        int m=i;
        quicksort(x,m-1);
        quicksort(m+1,y);
    }
}

int cautare_binara(int x,int y,int nr)
{   if(nr>=a[y])
    return y;
    if(x<=y)
    {
        int m = (x+y)/2;
        if((a[m]<=nr)&&(a[m+1]>nr))
            return m;
        else
        {
            if(a[m]>nr)
            return cautare_binara(x,m-1,nr);
        else
            return cautare_binara(m+1,y,nr);
        }
    }
}

void solutie()
{
    for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++)
    {
      s=a[i]+a[j];
      r=cautare_binara(1,n,s);
      if(r-j>0)
      k=k+r-j;
    }
    g<<k;
}

int main()
{
    citire();
    quicksort(1,n);
    solutie();
    f.close();
    g.close();
    return 0;
}