Pagini recente » Cod sursa (job #358699) | Cod sursa (job #817237) | Cod sursa (job #2736149) | Cod sursa (job #2725039) | Cod sursa (job #716236)
Cod sursa(job #716236)
#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;
}