Pagini recente » Cod sursa (job #2922940) | Cod sursa (job #841372) | Cod sursa (job #1763926) | Cod sursa (job #1241335) | Cod sursa (job #336719)
Cod sursa(job #336719)
#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;
}