Cod sursa(job #340405)

Utilizator vlad.maneaVlad Manea vlad.manea Data 14 august 2009 16:08:51
Problema Restante Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 8.2 kb
#include <cstdio>
#define nmax (36666)
#define sigm (26)

int N, A;
char strg[nmax][sigm], M[sigm][nmax], L[nmax];
int ind[nmax], ind2[nmax];

int compare(int i1, int i2)
{
	if (L[i1] < L[i2])
		return -1;

	if (L[i2] < L[i1])
		return 1;

	for (int i = 0; i < 26; ++i)
		if (M[i][i1] < M[i][i2])
			return -1;
		else if (M[i][i2] < M[i][i1])
			return 1;

	return 0;
}

void msort(int l, int r)
{
	if (l >= r)
		return;

	int m = (l+r)/2, i, j, k;

	msort(l, m);
	msort(m+1, r);

	for (i = k = l, j = m+1; i <= m && j <= r;)
		if (compare(ind[i], ind[j]) <= 0)
			ind2[k++] = ind[i++];
		else
			ind2[k++] = ind[j++];

	while (i <= m)
		ind2[k++] = ind[i++];

	while (j <= r)
		ind2[k++] = ind[j++];

	for (k = l; k <= r; ++k)
		ind[k] = ind2[k];
}

int main()
{
	int i, j;

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

	scanf("%d\n", &N);
	for (i = 0; i < N; ind[i] = i, ++i)
	{
		scanf("%s\n", &strg[i]);
		for (j = 0; strg[i][j]; ++j)
		{
			++M[strg[i][j]-'a'][i];
			++L[i];
		}
	}

	msort(0, N-1);

	if (compare(ind[0], ind[1]))
	{
		//printf("%s\n", strg[ind[0]]);
		++A;
	}

	for (i = 1, N--; i < N; ++i)
		if (compare(ind[i], ind[i-1]) && compare(ind[i], ind[i+1]))
		{
			//printf("%s\n", strg[ind[i]]);
			++A;
		}

	if (compare(ind[N-1], ind[N]))
	{
		//printf("%s\n", strg[ind[N]]);
		++A;
	}

	printf("%d\n", A);

	return 0;
}



/*#define PI (3.141592654)
#define EPS (0.001)
#define Flt float

Flt moveDir(Flt initialDirection = 0, Flt finalDirection = 0, Flt proportion = 0.5)
{
	// will be returned
	Flt ans;

	// divide
	while (proportion > 1+EPS)
		proportion /= 10;

	// at a proportion of 1.0, it goes to the final direction
	// at a proportion of 0.5, it goes to the average place
	// at a proportion of 0.0, it goes to the initial direction (unchanged)

	// set initial direction in [0, 2*PI]
	while (initialDirection > 2*PI+EPS)
		initialDirection -= 2*PI;
	while (initialDirection < -EPS)
		initialDirection += 2*PI;

	// set final direction in [0, 2*PI]
	while (finalDirection > 2*PI+EPS)
		finalDirection -= 2*PI;
	while (finalDirection < -EPS)
		finalDirection += 2*PI;

	// final direction must be bigger than initial direction. 
	// else they get swapped
	if (finalDirection < initialDirection-EPS)
	{
		initialDirection = initialDirection+finalDirection;
		finalDirection = initialDirection-finalDirection;
		initialDirection = initialDirection-finalDirection;
		proportion = 1-proportion;
	}

	if (finalDirection-initialDirection > PI+EPS)
		finalDirection -= 2*PI;

	ans = proportion*finalDirection+(1-proportion)*initialDirection;

	// answer must be between [0, 2*PI]
	while (ans > 2*PI+EPS)
		ans -= 2*PI;
	while (ans < -EPS)
		ans += 2*PI;

	return ans;
}

int main()
{
	float initialDirection = 1, finalDirection = 1, proportion = 0.5;
	
	while(-EPS > initialDirection || initialDirection > EPS || -EPS > finalDirection || finalDirection > EPS)
	{
		cin >> initialDirection >> finalDirection >> proportion;
		cout << moveDir(initialDirection, finalDirection, proportion) << '\n';
	}

	return 0;
}








/*#include <fstream>
using namespace std;

int expression(char*);
int orterm(char*);
int andterm(char*);
int xorterm(char*);
int factor(char*);

int P, N, M;
char expr1[512], expr2[512];
int gotused[32], used[2][32];

int expression(char *strg)
{
	
	int ans = orterm(strg), ams = 0;
	
	while (strg[P] == '|')
	{
		P++;
		
		ams = orterm(strg);
		ans = (ans || ams);
		

	}
	return ans;
}

int orterm(char *strg)
{
	
	int ans = xorterm(strg), ams = 0;
	
	while (strg[P] == '^')
	{
		P++;
		
		ams = xorterm(strg);
		ans = (ams && !ans || !ams && ans);
		
	}
	return ans;
}

int xorterm(char *strg)
{
	
	int ans = andterm(strg), ams = 0;
	
	while (strg[P] == '&')
	{
		P++;
		
		ams = andterm(strg);
		ans = (ans && ams);
		
	}
	return ans;
}

int andterm(char *strg)
{
	
	int ans;
	if (strg[P] == '~')
	{
		P++;
		
		ans = !factor(strg);
		

	}
	else
	{
		
		ans = factor(strg);
		
	}
	return ans;
}

int factor(char *strg)
{
	
	int ans = 0;
	if (strg[P] == '(')
	{
		P++;
		
		ans = expression(strg);
		
		P++;
		
	}
	else if ('a' <= strg[P] && strg[P] <= 'z')
	{	
		// caut elementul strg[P]-'a'
		int i;
		for (i = 1; i <= gotused[0] && gotused[i] != strg[P]-'a'; ++i);
		ans = M & ( 1 << (i-1));
		if (ans)
			ans = 1;
		P++;
		
	}
	else if (strg[P] == '~')
	{
		P++;
		ans = !factor(strg);
	}
	return ans;
}

int main()
{
	ifstream fin("logic.in");
	ofstream fout("logic.out");

	char c;
	fin >> N;
	fin.get(c);

	while (N--)
	{
		// citesc toate expresiile
		fin.getline(expr1, 256);
		fin.getline(expr2, 256);

		for (int i = 0; i < 26; used[0][i] = used[1][i] = 0, i++);

		// aflu variabilele implicate in prima expresie
		for (int i = 0; expr1[i]; i++)
			if ('a' <= expr1[i] && expr1[i] <= 'z')
				used[0][expr1[i]-'a'] = 1;

		// aflu variabilele implicate in a doua expresie
		for (int i = 0; expr2[i]; i++)
			if ('a' <= expr2[i] && expr2[i] <= 'z')
				used[1][expr2[i]-'a'] = 1;

		// retin
		for (int i = gotused[0] = 0; i < 26; ++i)
			if (used[0][i] && used[1][i])
				gotused[++gotused[0]] = i;
			else if (used[0][i] || used[1][i])
			{
				gotused[0] = 0;
				break;
			}

		if (gotused[0] == 0)
		{
			fout << "diferite\n";
			continue;
		}

		for (M = 0; M < (1 << gotused[0]); ++M)
		{
			P = 0;
			int ans1 = expression(expr1);
			P = 0;
			int ans2 = expression(expr2);

			if (ans1 != ans2)
				break;
		}

		if (M == (1 << gotused[0]))
			fout << "egale\n";
		else
			fout << "diferite\n";
	}

	fin.close();
	fout.close();

	return 0;
}























/*#define NMAX 128
#define MAXVAL (2147000000000ll)

long long N, M, K;
long long final[NMAX], minim[NMAX], maxim[NMAX], T[NMAX];
long long *prev[NMAX], *succ[NMAX];

void calcfin (long long i)
{
	if (prev[i][0])
	{
		long long maxim = -MAXVAL;
		for (long long j = 1; j <= prev[i][0]; ++j)
		{
			if (final[prev[i][j]] == MAXVAL)
				calcfin(prev[i][j]);

			if (final[prev[i][j]] > maxim)
				maxim = final[prev[i][j]];
		}

		final[i] = maxim + T[i];
		minim[i] = maxim;
	}
	else
	{
		final[i] = T[i];
		minim[i] = 0;
	}
}

void calcsta (long long i)
{
	if (succ[i][0])
	{
		long long minim = MAXVAL;
		for (long long j = 1; j <= succ[i][0]; ++j)
		{
			if (maxim[succ[i][j]] == -MAXVAL)
				calcsta(succ[i][j]);

			if (maxim[succ[i][j]] < minim)
				minim = maxim[succ[i][j]];
		}

		maxim[i] = minim - T[i];

	}
	else
	{
		maxim[i] = K-T[i];
	}
}

int main()
{
	FILE *fin = fopen("pm2.in", "r");
	FILE *fout = fopen("pm2.out", "w");

	fscanf(fin, "%lld", &N);
	for (long long i = 1; i <= N; ++i)
	{
		fscanf(fin, "%lld", &T[i]);
		succ[i] = (long long*)realloc(succ[i], sizeof(long long));
		succ[i][0] = 0;
		final[i] = MAXVAL;
	}

	for (long long i = 1; i <= N; ++i)
	{
		fscanf(fin, "%lld", &M);
		prev[i] = (long long*)realloc(prev[i], (M + 1) * sizeof(long long));
		prev[i][0] = M;
		for (long long j = 1; j <= M; ++j)
		{
			fscanf(fin, "%lld", &prev[i][j]);
			succ[prev[i][j]][0]++;
		}
	}

	for (long long i = 1; i <= N; ++i)
	{
		succ[i] = (long long*)realloc(succ[i], (succ[i][0] + 1) * sizeof(long long));
		succ[i][0] = 0;
	}

	fseek(fin, 0, SEEK_SET);

	fscanf(fin, "%lld", &N);
	for (long long i = 1; i <= N; fscanf(fin, "%lld", &M), ++i);

	for (long long i = 1; i <= N; ++i)
	{
		fscanf(fin, "%lld", &M);
		for (long long j = 1; j <= M; ++j)
		{
			fscanf(fin, "%lld", &prev[i][j]);
			succ[prev[i][j]][++succ[prev[i][j]][0]] = i;
		}
	}

	for (long long i = 1; i <= N; ++i)
		if (final[i] == MAXVAL)
			calcfin(i);

	K = -MAXVAL;
	for (long long i = 1; i <= N; ++i)
		if (final[i] > K)
			K = final[i];

	fprintf(fout, "%lld\n", K);

	for (long long i = 1; i <= N; ++i)
		maxim[i] = -MAXVAL;

	for (long long i = 1; i <= N; ++i)
		if (maxim[i] == -MAXVAL)
			calcsta(i);

	for (long long i = 1; i <= N; ++i)
		fprintf(fout, "%lld %lld\n", minim[i], maxim[i]);
	
	fclose(fin);
	fclose(fout);

	return 0;
}*/