Cod sursa(job #716271)

Utilizator teodora.petrisorPetrisor Teodora teodora.petrisor Data 18 martie 2012 15:34:24
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include<fstream>
#include<iostream>
using namespace std;

struct deque
{
	int n;
	int* elems;
};

/*
 * 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 removeFirst(deque& a)
{
	for (int i = 1; i<= a.n; i++)
		a.elems[i-1] = a.elems[i];
	a.n --;
}

/*
 * Remove last element from deque
 */
void removeLast(deque& a)
{
	a.n --;
}

/*
 * Add element to beginning of deque
 */
void appendFirst(deque& a, int el)
{
	a.n++;
	for(int i = a.n; i>1; i--)
		a.elems[i] = a.elems[i-1];
	a.elems[1] = el;
}


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;


	ifstream inFile;
	ofstream outFile;

	inFile.open("secventa.in");

	inFile>>n;
	inFile>>k;

	a.n = n;

	for (int i = 1; i<=n; i++)
		inFile>>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];
			removeFirst(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[a.n];
				removeLast(a);
				appendFirst(a, tmp);
				aux --;
			}
		}

	}

	inFile.close();

	outFile.open("secventa.out");

	outFile<<sPos<<" "<<fPos<<" "<<min;

	outFile.close();

	return 0;

}