Cod sursa(job #170424)

Utilizator tm_raduToma Radu tm_radu Data 2 aprilie 2008 19:04:20
Problema Restante Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NM 36001
using namespace std;

int n, i, j, k;
char c[NM][20];
int s[30];
char cu;
int nrsol;

void Qsort(int st, int dr);

int main()
{
    freopen("restante.in", "r", stdin);
    freopen("restante.out", "w", stdout);
    scanf("%d", &n);
    for ( i = 1; i <= n; i++ )
    {
        for ( j = 1; j <= 26; s[j] = 0, j++ );
        scanf("%c", &cu);
        scanf("%s", &c[i]);
        for ( j = strlen(c[i])-1; j >= 0; j-- )
            s[(int)(c[i][j]-'a'+1)]++;
        k = 0;
        for ( j = 1; j <= 26; j++ )
            while ( s[j] )
                c[i][k] = (char)(j-1+'a'),
                k++, s[j]--;
    }
    sort(c[i]+1, c[i]+n);
    for ( i = 1; i <= n; i++ )
        if ( i == n || strcmp(c[i], c[i+1]) != 0 )
            nrsol++;
        else
        {
            j = i+1;
            while ( j <= n && strcmp(c[i], c[j]) == 0 ) j++;
            i = j-1;
        }
    printf("%d\n", nrsol);
        
    return 0;
}

void Qsort(int st, int dr)
{
    int i = st-1;
    int j = dr+1;
    do
    {
        do { i++; } while ( strcmp(c[i], c[st]) <= 0 );
        do { j--; } while ( strcmp(c[st], c[j]) <= 0 );
        if ( i <= j )
        {
            char aux[20];
            strcpy(aux, c[i]);
            strcpy(c[i], c[j]);
            strcpy(c[j], aux);
        }
    } while ( i <= j );
    if ( i < dr ) Qsort(i, dr);
    if ( st < j ) Qsort(st, j);
}