Cod sursa(job #340515)

Utilizator mlazariLazari Mihai mlazari Data 15 august 2009 08:29:30
Problema Restante Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include<stdio.h>
#include<string.h>

#define NMAX 360001

int n,i,l[NMAX];
char s[NMAX][19];

void swap(char &c1,char &c2) {
  char aux=c1;
  c1=c2;
  c2=aux;
}

void swap(int &c1,int &c2) {
  int aux=c1;
  c1=c2;
  c2=aux;
}

void HeapSort(char *h,int n) {
  int x,y,i;
  for(i=2;i<=n;i++) {
    x=i;
    while(x>1)
     if(h[x]>h[x>>1]) {
       swap(h[x],h[x>>1]);
       x>>=1;
     }
     else x=1;
  }
  for(i=n-1;i>0;i--) {
    swap(h[1],h[i+1]);
    x=1;
    while((x<<1)<=i) {
      y=x;
      if(h[x<<1]>h[y]) y=x<<1;
      if(((x<<1)<i)&&(h[(x<<1)+1]>h[y])) y=(x<<1)+1;
      if(y!=x) {
        swap(h[x],h[y]);
        x=y;
      }
      else x=i;
    }
  }
}

void HeapSort2() {
  int x,y,i;
  char aux[20];
  for(i=2;i<=n;i++) {
    x=i;
    while(x>1)
     if(strcmp(s[x]+1,s[x>>1]+1)>0) {
       strcpy(aux,s[x]+1);
       strcpy(s[x]+1,s[x>>1]+1);
       strcpy(s[x>>1]+1,aux);
       x>>=1;
     }
     else x=1;
  }
  for(i=n-1;i>0;i--) {
    strcpy(aux,s[1]+1);
    strcpy(s[1]+1,s[i+1]+1);
    strcpy(s[i+1]+1,aux);
    x=1;
    while((x<<1)<=i) {
      y=x;
      if(strcmp(s[x<<1]+1,s[y]+1)>0) y=x<<1;
      if(((x<<1)<i)&&(strcmp(s[(x<<1)+1]+1,s[y]+1)>0)) y=(x<<1)+1;
      if(y!=x) {
        strcpy(aux,s[x]+1);
        strcpy(s[x]+1,s[y]+1);
        strcpy(s[y]+1,aux);
        x=y;
      }
      else x=i;
    }
  }
}

int nr_orig() {
  if(n==1) return 1;
  int i,no=0;
  if(strcmp(s[1]+1,s[2]+1)) no++;
  if(strcmp(s[n]+1,s[n-1]+1)) no++;
  for(i=2;i<n;i++)
   if(strcmp(s[i]+1,s[i-1]+1)&&strcmp(s[i]+1,s[i+1]+1)) no++;
  return no;
}

int main() {
  freopen("restante.in","r",stdin);
  freopen("restante.out","w",stdout);
  scanf("%d\n",&n);
  for(i=1;i<=n;i++) {
    fgets(s[i]+1,19,stdin);
    l[i]=strlen(s[i]+1)-1;
    HeapSort(s[i],l[i]);
  }
  HeapSort2();
  printf("%d\n",nr_orig());
  return 0;
}