Pagini recente » Statistici Alexandra Sicobean (ale.sicobean) | Monitorul de evaluare | Diferente pentru numerele-sprague-grundy intre reviziile 15 si 14 | Monitorul de evaluare | Cod sursa (job #127968)
Cod sursa(job #127968)
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define FIN "restante.in"
#define FOUT "restante.out"
#define MAX_N 36005
char A[MAX_N][20];
int n, i;
void preproc ()
{
int i, j;
int a[1 << 5];
for (i = 1; i <= n; ++i)
{
int L = strlen (A[i]);
memset (a, 0, sizeof (a));
for (j = 0; j < L; ++j)
++a[A[i][j] - 96];
int k = 0;
for (j = 1; j <= 26; ++j)
while (a[j]--)
A[i][k++] = j + 96;
}
}
int cmp (int i, int j)
{
int l1 = strlen (A[i]) - 1;
int l2 = strlen (A[j]) - 1;
if (l2 < l1) return 1;
if (l1 < l2) return 0;
for (int k = 0; k <= l1; ++k)
if (A[i][k] < A[j][k]) return 0;
else if (A[i][k] > A[j][k]) return 1;
return 1;
}
int part (int st, int dr)
{
int i, j, s = 1;
i = st;
j = dr;
while (i < j)
{
if (cmp (i, j))
{
char x[20] = "";
memcpy (x, A[i], sizeof (x));
memcpy (A[i], A[j], sizeof (A[j]));
memcpy (A[j], x, sizeof (x));
s = 1 - s;
}
if (s) ++i; else --j;
}
return i;
}
void sort (int st, int dr)
{
if (st < dr)
{
int p = part (st, dr);
sort (st, p - 1);
sort (p + 1, dr);
}
}
void solve ()
{
int i, j;
int sol = 0;
for (i = 1; i <= n; ++i)
if (memcmp (A[i], A[i - 1], 19) && memcmp (A[i], A[i + 1], 19))
++sol;
printf ("%d\n", sol);
}
int main ()
{
freopen (FIN, "r", stdin);
freopen (FOUT, "w", stdout);
scanf ("%d\n", &n);
for (i = 1; i <= n; ++i)
gets (A[i]);
preproc ();
sort (1, n);
solve ();
return 0;
}