Pagini recente » Cod sursa (job #584336) | Cod sursa (job #1086668) | Cod sursa (job #1504739) | Cod sursa (job #101500) | Cod sursa (job #50706)
Cod sursa(job #50706)
/*
*
*
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;
}