Cod sursa(job #20315)

Utilizator piroslPiros Lucian pirosl Data 21 februarie 2007 02:14:41
Problema Secv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include<iostream>
#include<fstream>
using namespace std;

class nod 
{
public:
	int a;
	class nod* link;
};

void adauga(nod* &head, int a)
{
	nod* tmpNod = new nod();
	tmpNod->a = a;
	tmpNod->link = NULL;
	if(head == NULL)
	{
		head = tmpNod;
	}
	else
	{
		nod* parc = head;
		nod* prev = head;
		tmpNod->link = parc;
		while(parc != NULL && parc->a < a)
		{
			prev = parc;
			parc = parc->link;
			tmpNod->link = parc;
		}
		if(parc!= NULL && parc->a == a)
		{
			delete tmpNod;
			return;
		}
		if(parc == head)
		{
			head = tmpNod;
		}
		else
		{
			prev->link = tmpNod;
		}
		
	}
}

void parcurge(nod* head)
{
	nod* p = head;
	while(p != NULL)
	{
		cout << p->a <<" ";
		p=p->link;
	}
}

int getPos(int k, int num, int* numere, int n)
{
	for(int i=k+1;i<n;i++)
	{
		if(numere[i] == num)
		{
			return i;
		}
	}
	return -1;
}

int getMin(nod* h, int s, int* numere, int n)
{
	int start = s;
	int end = s;

	int nextPos = s;
	while(h != NULL) 
	{
		nextPos = getPos(nextPos, h->a, numere, n);
		if(nextPos == -1)
			return -1;
		if(h->link == NULL)
			end = nextPos;
		h = h->link;
	}
	return (end-start+1);
}

int main(void) 
{
	ifstream in;
	ofstream out;
	int* numere;
	nod* head = NULL;
	int min = 5001;
	bool hasMin = false;

	in.open("secv.in", ios::in);
	out.open("secv.out", ios::out);

	int n;
	in >> n;

	numere = new int[n];

	for(int i=0;i<n;i++)
	{
		int a;
		in >> a;
		numere[i] = a;
		adauga(head, a);
	}

	cout<<endl;
//	parcurge(head);
	
	if(n == 0)
	{
		out << 0;		
	}
	else
	{
		int a = head->a;
		for(int i=0;i<n;i++)
		{
			if(numere[i] == a) 
			{
				int m = getMin(head->link, i, numere,n);
				if(m > -1)
				{
					if(m < min)
					{
						min = m;
						hasMin = true;
					}
				}
			}
		}
	}

	if(hasMin)
		out << min;
	else
		out << -1;

	in.close();
	out.close();

	delete[] numere;
	
	return 0;
}