Cod sursa(job #57895)

Utilizator peanutzAndrei Homorodean peanutz Data 3 mai 2007 15:46:09
Problema Secv Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <stdio.h>
#include <memory.h>

#define NMAX 5010

long long int a[NMAX], c[NMAX], aux[NMAX];
long long int n, h;
long long int min = 32000;

void read()
{
	int i;

	scanf("%lld\n", &n);

	for(i = 0; i < n; ++i)
	{
		scanf("%lld ", &a[i]);
	}
}

long long int divide(long long int p,long long int q)
{
	long long int st = p, dr = q;
	long long int x = aux[st];

	while(st < dr)
	{
		while(st < dr && x <= aux[dr]) --dr;
		aux[st] = aux[dr];

		while(st < dr && x >= aux[st]) ++st;
		aux[dr] = aux[st];
	}

	aux[st] = x;

	return st;
}

void qsort(long long int p, long long int q)
{
	int m = divide(p, q);

	if(p < m)
		qsort(p, m-1);
	if(q > m)
		qsort(m+1, q);
}

void do_c()
{
	long long int i;

	c[0] = aux[0];
	h = 1;

	for(i = 1; i < n; ++i)
	{
		if(aux[i] != c[h-1])
		{
			c[h++] = aux[i];
		}
	}
}
void find()
{
	long long int i, j, k;

	for(i = 0; i < n; ++i)
	{
		if(a[i] == c[0])
		{
			for(k = 1, j = i+1; j < n; ++j)
			{
				if(a[j] == c[k])
				{
					k++;
				}
				if(k == h)
				{
					if(j-i+1 < min)
						min = j-i+1;
					break;
				}
			}
		}
	}
}

int main()
{
	freopen("secv.in", "r", stdin);
	freopen("secv.out", "w", stdout);

	read();

	memcpy(aux, a, sizeof(a));

	qsort(0, n-1);

	do_c();

	find();

	printf("%lld\n", min);

	fclose(stdin);
	fclose(stdout);

	return 0;
}