Cod sursa(job #125501)

Utilizator DastasIonescu Vlad Dastas Data 20 ianuarie 2008 14:08:04
Problema Restante Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <cstdio>
#include <algorithm>
#include <cstring>

const int maxn = 36002;
const int maxl = 18;

FILE *in = fopen("restante.in","r"), *out = fopen("restante.out","w");

int n;
char a[maxn][maxl];

int cnt;

char temp[maxl];
int partition(int p, int q)
{
    int i = p - 1;
    int j = q + 1;

    do
    {
        do
        {
            --j;
        } while ( strcmp(a[p], a[j]) < 0 );

        do
        {
            ++i;
        } while ( strcmp(a[p], a[i]) > 0 );

        if ( i < j )
        {
            strcpy(temp, a[i]);
            strcpy(a[i], a[j]);
            strcpy(a[j], temp);
        }

    } while ( i < j );

    return j;
}

void quicksort(int top, int bottom)
{
    int middle;
    if ( top < bottom )
    {
        middle = partition(top, bottom);
        quicksort(top, middle);
        quicksort(middle+1, bottom);
    }

    return;
}

void read()
{
    fscanf(in, "%d", &n);

    int k;
    for ( int i = 1; i <= n; ++i )
    {
        fscanf(in, "%s", a[i]);
        int k = strlen(a[i]);

        std::sort(a[i], a[i] + k);
    }

    quicksort(1, n);
}

int main()
{
    read();

    if ( strcmp(a[1], a[2]) )
        ++cnt;
    if ( strcmp(a[n-1], a[n]) )
        ++cnt;

    for ( int i = 2; i < n; ++i )
        if ( strcmp(a[i-1], a[i]) && strcmp(a[i], a[i+1]) )
            ++cnt;

    fprintf(out, "%d\n", cnt);

	return 0;
}