Cod sursa(job #125083)

Utilizator IoannaPandele Ioana Ioanna Data 20 ianuarie 2008 11:17:09
Problema Restante Scor 30
Compilator cpp Status done
Runda preONI 2008, Runda 3, Clasa a 9-a Marime 1.5 kb
#include<stdio.h>
#include<string.h>
char x[36010][20];
long n,v[36010],k,nr;

void read()
{
char c;
scanf("%ld",&n);
scanf("%c",&c);
}

long part(long st,long dr)
{
char aux;
long i,j;
char p;
p=x[k][(st+dr)/2];
i=st-1;
j=dr+1;
while (1)
      {
       do {i++;} while(x[k][i]<p);
       do {j--;} while(x[k][j]>p);
       if (i<j)
	  {
	   aux=x[k][i];
	   x[k][i]=x[k][j];
	   x[k][j]=aux;
	  }
       else return j;
      }
}

void quicks(long st,long dr)
{
long p;
if (st<dr)
   {
    p=part(st,dr);
    quicks(st,p);
    quicks(p+1,dr);
   }

}

long part1(long st,long dr)
{
long i,j,p;
char aux[20];
i=st-1;
j=dr+1;
p=(st+dr)/2;
while (1)
      {
      do {i++;} while (strcmp(x[i],x[p])<0);
      do {j--;} while (strcmp(x[j],x[p])>0);
      if (i<j)
	 {
	  strcpy(aux,x[i]);
	  strcpy(x[i],x[j]);
	  strcpy(x[j],aux);
	 }
      else return j;
      }

}

void quicks1(long st,long dr)
{
long p;
if (st<dr)
   {
    p=part1(st,dr);
    quicks1(st,p);
    quicks1(p+1,dr);
   }
}

void rez()
{
long i;
i=1;
while (i<=n)
      {
       scanf("%s",x[i]);
       v[i]=strlen(x[i]);
       k=i;
       quicks(0,v[i]-1);
       i++;
      }
quicks1(1,n);
long l=1;
for (i=1;i<=n;i++)
    {
     if (strcmp(x[i],x[i+1]))
	{
	 if (l==1)
	     nr++;
	 l=1;
	}
    else l++;
    }
}

int main()
{
freopen("restante.in","r",stdin);
freopen("restante.out","w",stdout);
read();
rez();
printf("%ld",nr);
fcloseall();
return 0;
}