Cod sursa(job #336719)

Utilizator iulia609fara nume iulia609 Data 1 august 2009 12:21:05
Problema Restante Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include<stdio.h>
#include <cstdio>
#include<algorithm>
#include<string.h>
#define dim 36001
#define cif 17
using namespace std;

int A[dim][cif], c[dim], b[dim];
char s[cif];
int n,max;

/*int comp(int a, int b)
{
	return strcmp(A[a], A[b]);	
}
*/

void counting_sort(int A[dim][cif], int x, int max)
{  int j,i, aux,t,cont;

	for(i = 1; i <= dim; i++) c[i] = 0,b[i] = 0;
	for(j = 1; j <= n; j++)
		//{
			c[A[j][x]]++;
		 //if(A[x][j] > k) k = a[x][j];
		//}
	for(i = 1; i <= 26; i++)
		c[i] += c[i-1];
	for(j = n; j >=1; j--)
		b[c[A[j][x]]] = A[j][x], c[A[j][x]]--;
	
	i = 1; cont = 1;
	while(i <= n)
		{
			for(j = i; j <=n; j++)
				if(A[j][x] == b[i])
					{
						if(j == i) {cont++; break;}
						for(t = 1; t <= max; t++)
							aux = A[j][t], A[j][t] = A[cont][t], A[cont][t] = aux;
						cont++;
						break;
					}
			i++;
		}
}


void radix_sort(int A[dim][cif], int max)
{  int i;
	
	for(i = max; i >= 0; i--)
		counting_sort(A, i, max);
	
}


int main()
{ int i, j, m, k,max,ok;
	FILE *f = fopen("restante.in", "r");
	FILE *g = fopen("restante.out", "w");
	
	fscanf(f, "%d", &n);
	
	max = 0;
	for(i = 1; i <= n; i++)
		{
			//o[i] = i;
			fscanf(f, "%s", &s);
			m = strlen(s);
			if(m > max) max = m;
			for(j = 0; j < m; j++) 
				A[i][j+1] = (int)s[j] - 'a' +1;
			sort(A[i], A[i]+m+1);
		}
	
	
	radix_sort(A, max);
	
	k = 0;
	for(i = 2; i <= n; i++)
	   {ok = 1;
		for(j = 1; j <= max; j++)
				if(A[i][j] != A[i-1][j]) 
				{
					ok = 0;
					break;
				}	
		 if(ok) k++;
		}
	
	
	fprintf(g, "%d\n", n-k*2);
	
	
	fclose(f);
	fclose(g);
	return 0;
}