Cod sursa(job #125249)

Utilizator savimSerban Andrei Stan savim Data 20 ianuarie 2008 12:18:29
Problema Restante Scor 50
Compilator cpp Status done
Runda preONI 2008, Runda 3, Clasele 5-8 Marime 1.95 kb
#include <stdio.h>
#include <string.h>
char c[17];
int n,i,j,k,nr;
short int a[36001][27],b[36001][27];
short int val[36001];
void inter(int p, int q, int lvl)
{
	 int r=(p+q)/2,x,y,s,i;
     x=p;y=r+1;k=0;
	 while (x<=r && y<=q)
     {
           if (a[x][lvl]<a[y][lvl])      
           {
               k++;
               for (s=lvl; s<=27; s++)
				   b[k][s]=a[x][s];
			   x++;
		   }
		   else
		   {
			   k++;
			   for (s=lvl; s<=27; s++)
				   b[k][s]=a[y][s];
			   y++;
		   }
	 }
     while (x<=r)
     {
         k++;
         for (s=lvl; s<=27; s++)
             b[k][s]=a[x][s];
		 x++;
	 }
	 while (y<=q)
	 {
		 k++;
		 for (s=lvl; s<=27; s++)
			 b[k][s]=a[y][s];
		 y++;
	 }
	 k=0;
	 for (i=p; i<=q; i++)
     {
         k++;
		 for (s=lvl; s<=27; s++)
             a[i][s]=b[k][s];    
     }
}
void merge(int p, int q, int lvl)
{
     int r=(p+q)/2;     
     if (p==q) return;
     merge(p,r,lvl);
     merge(r+1,q,lvl);
	 inter(p,q,lvl);
     if (q<=p+1) return;
}
int main()
{
    
    freopen("restante.in","r",stdin);
    freopen("restante.out","w",stdout);

	scanf("%d",&n);

	for (i=1; i<=n; i++)
	{
		scanf("%s",c);
		for (j=0; j<=strlen(c)-1; j++)
			a[i][int(c[j]-96)]++;
	}


	for (i=0; i<=26; i++)
	{
		for (j=1; j<=27; j++)
			a[0][j]=a[1][j];
		int p1=1,p2=0;
		for (j=1; j<=n; j++)
		{
			int t;
			int gas=1;
			for (t=0; t<=i; t++)
				if  (a[j][t]!=a[j-1][t])
				{
					gas=0;
					break;
				}
			if (gas==1) p2++;
			else
			{
				if (p1!=p2) merge(p1,p2,i+1);
				p1=j;p2=j;
			}

		}
		if (p2==n && p1!=p2) merge(p1,p2,i+1);
	}
	nr=0;
	for (i=1; i<=27; i++)
		a[0][i]=0;

	for (i=1; i<=n-1; i++)
	{
		int gas=1;
		for (j=1; j<=27; j++)
			if (a[i][j]!=a[i+1][j])
			{
				gas=0;
				break;
			}
		if (gas==1)
		{
			val[i]=1;
			val[i+1]=1;
		}
	}
	for (i=1; i<=n; i++)
		if (!val[i]) nr++;
	printf("%d\n",nr);
	return 0;
}