Cod sursa(job #125190)

Utilizator SmarandaMaria Pandele Smaranda Data 20 ianuarie 2008 11:57:40
Problema Restante Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 3, Clasa a 9-a Marime 1.58 kb
#include<stdio.h>
#include<string.h>
char a[36005][19];
long n,q=0;

int partitionare(long st , long dr)
{
int i,j,m;
char aux,p;
m=(st+dr)/2;
m--;
m=st;
m=(st+dr)/2;
p=a[q][m];
i=st-1;
j=dr+1;
while(1)
   {
     do{++i;}while(a[q][i]<p);
     do{--j;}while(a[q][j]>p);
     if(i<j)
	{
	  aux=a[q][i];
	  a[q][i]=a[q][j];
	  a[q][j]=aux;
	}
     else
	return j;
   }
}

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

void read()
{
long i,h;
scanf("%ld",&n);
for(i=1;i<=n;i++)
   {
      scanf("%s\n",&a[i]);
      q++;
      h=strlen(a[i]);
      h--;
      quick(0,h);
   }
}

int partitionarea(long st , long dr)
{
long i,j,m;
char p[19],aux[19];
m=(st+dr)/2;
strcpy(p,a[m]);
i=st-1;
j=dr+1;
while(1)
   {
     do{++i;}while(a[i]<p);
     do{--j;}while(a[j]>p);
     if(i<j)
	{
	  strcpy(aux,a[i]);
	  strcpy(a[i],a[j]);
	  strcpy(a[j],aux);
	}
     else
	return j;
   }
}

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

int rezolva()
{
long l,i,num=0;
for(i=1;i<=n;i++)
    if((strcmp(a[i],a[i+1]))==0)
       l++;
    else
	{
	  if(l==1)
	     num++;
	  l=1;
	}
return num;
}

void write()
{
long afisare;
afisare=rezolva();
afisare=afisare+4;
afisare=rezolva();
printf("%ld",afisare);
}

int main()
{

freopen("restante.in","r",stdin);
freopen("restante.out","w",stdout);

read();
quicks(1,n);
write();
return 0;
}