Cod sursa(job #340204)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 13 august 2009 17:05:07
Problema Restante Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n;
char v[36005][20];

void read()
{
	freopen("restante.in","r",stdin);
	freopen("restante.out","w",stdout);
	scanf("%d\n",&n);
	int i;
	for(i=1;i<=n;i++)
	{
		gets(v[i]+1);
		v[i][0]=strlen(v[i]+1);
		sort(v[i]+1,v[i]+v[i][0]+1);
	}
}

int part(int st, int dr)
{
	int i,j,m;
	char aux[20],p[20];
	m=(st+dr)>>1;
	memcpy(p,v[m],sizeof(p));
	i=st-1;
	j=dr+1;
	while(1)
	{
		do{++i;}while(strcmp(v[i],p)<0);
		do{--j;}while(strcmp(v[j],p)>0);
		if(i<j)
		{
			memcpy(aux,v[i],sizeof(aux));
			memcpy(v[i],v[j],sizeof(v[j]));
			memcpy(v[j],aux,sizeof(aux));
		}
		else
			return j;
	}
}

void quick(int st, int dr)
{
	int p;
	if(st<dr)
	{
		p=part(st,dr);
		quick(st,p);
		quick(p+1,dr);
	}
}

void rez()
{
	int i,j,nr=0;
	for(i=1;i<=n;)
		if(strcmp(v[i],v[i+1])==0)
		{
			for(j=i+2;j<=n;j++)
				if(strcmp(v[i],v[j]))
					break;
			i=j;
		}
		else
		{
			i++;
			nr++;
		}
	printf("%d\n",nr);
}

int main()
{
	read();
	quick(1,n);
	rez();
	return 0;
}