Cod sursa(job #125270)

Utilizator hadesgamesTache Alexandru hadesgames Data 20 ianuarie 2008 12:21:57
Problema Restante Scor 70
Compilator cpp Status done
Runda preONI 2008, Runda 3, Clasele 5-8 Marime 2.16 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int a[36001][100],d[100],c[100],b[36001],put[100][100];
void inmultire1(int x)
{
	int i,minte=0;
	put[x][0]=put[x-1][0];
	for (i=1;i<=put[x-1][0];i++)
	{
		put[x][i]=17*put[x-1][i]+minte;
		minte=put[x][i]/10;
		put[x][i]%=10;
	}
	while (minte)
	{
		put[x][0]++;
		put[x][put[x][0]]=minte%10;
		minte/=10;
	}
}
void inmultire2(int x,int y)
{
	int i,minte=0;
	if (x==0)
	{
		d[0]=1;
		d[1]=0;
		return;
	}
	d[0]=put[y][0];
	for (i=1;i<=put[y][0];i++)
	{
		d[i]=put[y][i]*x+minte;
		minte=d[i]/10;
		d[i]%=10;
	}
	while (minte)
	{
		d[0]++;
		d[d[0]]=minte%10;
		minte/=10;
	}
}
void adunare(int x)
{
	int i,minte=0;
	for (i=1;i<=d[0]||i<=a[x][0];i++)
	{
		if (i>a[x][0])
			a[x][i]=0;
		if (i<=d[0])
			a[x][i]+=d[i];
		a[x][i]+=minte;
		minte=a[x][i]/10;
		a[x][i]%=10;
			
	}
	if (d[0]>a[x][0])
		a[x][0]=d[0];
	if (minte)
	{
		a[x][0]++;
		a[x][a[x][0]]=1;
	}
}
int comp(int x,int y)
{
	int i;
	if (a[x][0]>a[y][0])
		return 1;
	if (a[x][0]<a[y][0])
		return -1;
	for (i=a[x][0];i>=1;i--)
	{
		if (a[x][i]>a[y][i])
			return 1;
		if (a[x][i]<a[y][i])
			return -1;
	}
	return 0;
}
 int compare( const void* a, const void* b ) {
   int* arg1 = (int*) a;
   int* arg2 = (int*) b;
   return comp(*arg1,*arg2);
   /*if( *arg1 < *arg2 ) return -1;
   else if( *arg1 == *arg2 ) return 0;
   else return 1;*/
 }     
 
int main()
{
	FILE *in,*out;
	int n,i,j,nr=0,x,e;
	char s[50];
	in=fopen("restante.in","r");
	out=fopen("restante.out","w");
	fscanf(in,"%d",&n);
	put[0][0]=1;
	put[0][1]=1;
	for (i='b';i<='z';i++)
	{
		inmultire1(i-'a');
	}
		
	for (i=1;i<=n;i++)
	{
		b[i]=i;
		fscanf(in,"%s",s);
		x=strlen(s);
		for (j='a';j<='z';j++)
			c[j-'a']=0;
		for (j=0;j<x;j++)
		{
			c[s[j]-'a']++;
		}
		a[i][0]=0;
		for (j='a';j<='z';j++)
		{
			inmultire2(c[j-'a'],j-'a');
			adunare(i);
		}
			
		x=0;
	}
	qsort(b+1,n,sizeof(b[1]),compare);
	for (i=1;i<=n;i++)
	{
		e=1;
		while(comp(b[i],b[i+1])==0)
		{
			i++;
			e=0;
		}
		if (e)
			nr++;
	}
	fprintf(out,"%d\n",nr);
	fclose(in);
	fclose(out);
	return 0;
}