Pagini recente » Cod sursa (job #316236) | Cod sursa (job #954361) | Cod sursa (job #1862727) | Cod sursa (job #3198363) | Cod sursa (job #1811322)
#include <cstdio>
#include <algorithm>
#include <bitset>
using namespace std;
int a[36001][17];
int b[36001][17];
int ff[30];
int compar (int x,int y){
for (int i=0;i<=a[x][0];i++){
if (a[x][i]>a[y][i])
return 0;
else if (a[x][i]<a[y][i])
return 1;
}
return 2;
}
void muta (int x,int y){
for (int i=0;i<=a[y][0];i++)
b[x][i]=a[y][i];
}
void transf (int st,int dr){
for (int i=st;i<=dr;i++)
for (int j=0;j<=b[i][0];j++)
a[i][j]=b[i][j];
}
void interclas (int st,int mid,int dr){
int i,j,k=st-1;
i=st;
j=mid+1;
while (i<=mid && j<=dr){
if (compar (i,j)){
k++;
muta (k,i);
i++;
}
else {
k++;
muta (k,j);
j++;
}
}
while (i<=mid){
k++;
muta (k,i);
i++;
}
while (j<=dr){
k++;
muta (k,j);
j++;
}
transf (st,dr);
}
void merge (int st,int dr){
if (st<dr){
int mid=(st+dr)/2;
merge (st,mid);
merge (mid+1,dr);
interclas (st,mid,dr);
}
}
int main()
{
FILE *fin=fopen ("restante.in","r");
FILE *fout=fopen ("restante.out","w");
int n,i,uni,st,l;
char c;
fscanf (fin,"%d\n",&n);
for (i=1;i<=n;i++){
c=fgetc (fin);
while (c!='\n'){
l=c-'a'+1;
ff[l]++;
c=fgetc (fin);
}
for (int j=1;j<30;j++){
while (ff[j]){
a[i][++a[i][0]]=j;
ff[j]--;
}
}
}
merge (1,n);
uni=0;
st=0;
for (i=1;i<=n;i++){
if (compar(i,i-1)!=2){
uni++;
st=0;
}
else
if (st==0){
st=1;
uni--;
}
}
fprintf (fout,"%d",uni);
return 0;
}