Cod sursa(job #310221)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 1 mai 2009 23:16:02
Problema Restante Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <string.h>
#define N 36005
#define P  20
using namespace std;
char s[P];
int v[N][P],linii_sortate[N];
int n;
void citire()
{
	scanf("%d\n",&n);
	int i,t,j;
	for (i=1; i<=n; i++)
	{
		fgets(s+1,P,stdin);
		t=(int)strlen(s+1);
		for (j=1; j<=t && s[j]!='\n'; j++)
			v[i][++v[i][0]]=(int)s[j]-96;
	}
}
void sortare_litere()
{
	int i,j,x[P];
	for (i=1; i<=n; i++)
	{
		for (j=1; j<=v[i][0]; j++)
			x[j]=v[i][j];
		sort(x+1,x+v[i][0]+1);
		for (j=1; j<=v[i][0]; j++)
			v[i][j]=x[j];
	}
}
int compare (const void *p,const void *q)
{
	int x=*(int *)p; 
	int y=*(int *)q;
	if (v[x][0]<v[y][0])
		return -1;
	if (v[x][0]>v[y][0])
		return 1;
	for (int k=1; k<=v[x][0]; k++)
	{
		if (v[x][k]<v[y][k])
			return -1;
		if (v[x][k]>v[y][k])
			return 1;
	}
	return 0;
}
void sortare_cuvinte()
{
	for (int i=1; i<=n; i++)
		linii_sortate[i]=i;
	qsort(linii_sortate+1,n,sizeof(linii_sortate[0]),compare);	
}
void rezolvare()
{
	int i,j,rez=1,identic,pur=1;
	for (i=2; i<=n; i++)
	{
		if (v[linii_sortate[i]][0]==v[linii_sortate[i-1]][0])
		{
			identic=1;
			for (j=1; j<=v[linii_sortate[i]][0]; j++)
				if (v[linii_sortate[i]][j]!=v[linii_sortate[i-1]][j])
				{
					identic=0;
					break;
				}
			if (identic==0)
			{
				rez++;
				pur=1;
			}
			else
				if (pur)
				{
					rez--;
					pur=0;
				}
		}
		else
		{
			rez++;
			pur=1;
		}
	}
	printf("%d\n",rez);
}
int main()
{
    freopen("restante.in","r",stdin);
    freopen("restante.out","w",stdout);
    citire();
	sortare_litere();
	sortare_cuvinte();
	rezolvare();
    return 0;
}