Pagini recente » Cod sursa (job #2264372) | Cod sursa (job #3155841) | Cod sursa (job #1960925) | Cod sursa (job #1525503) | Cod sursa (job #115633)
Cod sursa(job #115633)
using namespace std;
#include <cstdio>
#include <algorithm>
#define maxn 801
int main()
{
int a[maxn], n; // stiva e mai rapida decat variabilele globale! ATENTIE sizeof(stiva)<1mb pt linux...pt borland <64kb parca
int i, j, k,cnt;
freopen("nrtri.in","r",stdin);
scanf("%d\n", &n); //citesc n
for(i=1;i<=n;++i) scanf("%d ", a+i); //citesc a[i]
sort(a+1, a+n+1); // sortez crescator
int nr=0;
for(i=1;i<n-1;++i)
for(j=i+1;j<n;++j) // aleg 2 pozitii i<j
{
// si calculez in O(logn) cate triunghiuri se pot forma cu cele 2 folosind o cautare binara
// am folosit o cautare binara mai smenoasa si mai performanta (de 3-4 ori mai rapida)
// ideea este sa fac salturi de 2^k
for(k=j+1, cnt=(1<<10); cnt ; cnt>>=1)
if(k+cnt<=n)
if(a[i]+a[j]>=a[k+cnt]) k+=cnt;
if(a[i]+a[j]>=a[j+1])
{
nr+=k-j;
// printf("%d %d %d\n", i, j, k);
}
}
freopen("nrtri.out","w",stdout);
printf("%d\n", nr); //afisez solutia
return 0;
}