Cod sursa(job #519895)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 6 ianuarie 2011 20:20:31
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <stdio.h>
#include <string>

FILE *fin = fopen("nrtri.in","r");
FILE *fout= fopen("nrtri.out","w");

int i,j,N,v[805],id[805],NR;
char s[8000];

void citire()
{
	fscanf(fin,"%d\n",&N);
	fgets(s,sizeof(s),fin);
	int L=strlen(s),p=0;
	for(i=0;i<=L;i++)
	{
		for(;s[i]==' ' && i<=L;i++);
		if(i==L) break;
		p++;
		for(;s[i]>='0'&&s[i]<='9'&&i<=L;i++)
			v[p]=10*v[p]+s[i]-'0';
	}
}

void mergesort(int st, int m, int dr)
{
	int aux[m-st+2],i,j,k;
	i=1; j=st;
	while(j<=m)
		aux[i++]=id[j++];
	i=1; k=st;
	while(j<=dr && k<j)
		if(v[aux[i]]<=v[id[j]])
			id[k++]=aux[i++];
		else
			id[k++]=id[j++];
	while(k<j)
		id[k++]=aux[i++];
}

void msort(int st, int dr)
{
	if(st<dr)
	{
		int m=st-(st-dr)/2;
		msort(st,m);
		msort(m+1,dr);
		mergesort(st,m,dr);
	}
}

int cb(int st, int dr)
{
	int m=st-(st-dr)/2;
	while(st<=dr)
	{
		if((v[id[m]]<=v[id[i]]+v[id[j]]&&v[id[m+1]]>v[id[i]]+v[id[j]]) || (m==N && v[id[m]]<=v[id[i]]+v[id[j]]))
			return m;
		else if(v[id[m]]<=v[id[i]]+v[id[j]])
			st=m+1;
		else dr=m-1;
		m=st-(st-dr)/2;
	}
	return 0;
}

void rez()
{
	for(i=1;i<=N-2;i++)
		for(j=i+1;j<=N-1;j++)
		{
			int p=cb(j+1,N);
			for(;p>=j+1;p--) NR++;
		}
}


int main()
{
	citire();
	for(i=1;i<=N;i++) id[i]=i;
	msort(1,N);
	rez();
	fprintf(fout,"%d",NR);
}