Cod sursa(job #716236)

Utilizator teodora.petrisorPetrisor Teodora teodora.petrisor Data 18 martie 2012 14:54:11
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb

#include<fstream>
using namespace std;

struct deque
{
	int n;
	int elems[500000];
};

/*
 * Append element to end of deque
 */
void append(deque a, int el)
{
	a.n ++;
	a.elems[a.n] = el;
}

/*
 * Remove element from beginning of deque
 */
void remove(deque a)
{
	for (int i = 1; i<= a.n; i++)
		a.elems[i-1] = a.elems[i];
	a.n --;
}

int getMin(deque a, int length)
{
	int min = 30001;
	for (int i = 1; i<= length; i++)
		if (a.elems[i] < min)
			min = a.elems[i];

	return min;
}

int main()
{
	int n, k, min = -30001, tmpMin;
	deque a;
	int sPos, fPos;

	int turns, length;

	fstream input("secventa.in", ios::in);

	input>>n;
	input>>k;

	a.n = n;

	for (int i = 1; i<=n; i++)
		input>>a.elems[i];

	length = n; // initialize max length with length of deque
	turns = n - length ; // initialize turns with difference between n and length


	while(length >= k)	// while the length of the deque is greater than the minimum length
	{
		tmpMin = getMin(a, length); // get the minimum in the sequence with the given length

		if (tmpMin > min)	// if temporary minimum is greater than the overall minimum, save min and sequence properties
		{
			sPos = 1 + n - (length + turns);
			fPos = sPos + length - 1;
			min = tmpMin;
		}

		if (turns > 0)
		{
			int aux = a.elems[1];
			remove(a);
			append(a, aux);
			turns --;
		}
		else
		{
			length--;	// search for shorter sequence
			turns = n - length;	// more turns than before
			int aux = turns - 1;
			while(aux > 0)	// restore deque
			{
				int tmp = a.elems[1];
				remove(a);
				append(a, tmp);
				aux --;
			}
		}

	}

	input.close();

	fstream output("secventa.out", ios::out);

	output<<sPos<<" "<<fPos<<" "<<min;

	output.close();

	return 0;

}