Question

Boring job One day, Rick got a sequence of N magic numbers. In order to find the latent code in the sequence, he decides to do the following operations with a magic parameter K: Step (1) Take out the first k numbers from current sequences into a temporary sequence ni namn, and pick the largest element Vmax out of these k numbers, then subtract 1 from the remaining K-1 elements. If there exist more than one largest element, choose the one with smaller index in temporary sequence. Step (2) Print the index (count from 1) of Vmax in the initial sequence, append the rest K-1 elements (with subtraction done) in temporary sequence back to the end of S. Repeat (1)(2) until s become empty. If the size of S is smaller than K, in step (1) just take out all the elements. Since Rick is too smart to be interested in doing this on his own, he asked his grandchild Morty to do this job for him. However, Morty is just not clever enough to do this job... Can you use your programming skill to help poor Morty? Input The first line of input is an integer T (1 <= T <= 10) indicating the number of test cases. Each test case will follow the format shown below: The first line: Two integers N and K showing the length of sequence and magic parameter in this test case. The second line: Nintegers m, 2,..., my showing magic numbers in the sequence. (1 <= N<= 1000, 1 <= mi<= 100000, 1 <=k 20 and k <N) Output Print a single line containing the desired sequence of indices with each index separated by a single space.

Topic:Data structures and algorithms programming

Compiler:C++ 11, flag: -static -std=c++0x

Answer 1

CODE:

#include<bits/stdc++.h>
using namespace std;

int minimum(int a,int b)
{
if(a<b)
return a;
return b;
}

int main()
{
int t,n,k;
int i,j,temp;
int cur_max,ind;
pair <int,int>p;
cin>>t;
while(t--)
{
cin>>n>>k;
deque <pair<int,int>>q; //Array of pairs containing value and its index
deque <pair<int,int>>d; //To store k elements
for(i=1;i<=n;i++)
{
cin>>temp;
q.push_back(make_pair(temp,i));
}
for(i=1;i<=n;i++) //loop n times for printing n elements
{
int loop=minimum(k,q.size());
cur_max=q.front().first;
ind=q.front().second;
for(j=1;j<=loop;j++)
{
p=q.front();
if(cur_max<p.first) //update maximum
{
cur_max=p.first;
ind=p.second;
}
q.pop_front();
d.push_back(p);
}
loop=d.size();
for(j=1;j<=loop;j++)
{
p=d.front();
d.pop_front();
if(ind!=p.second) //This element was not maximum amongst the k elements and will be inserted back
{
p.first--; //reduce by 1
q.push_back(p); //re-insert it
}
}
cout<<ind<<" "; //print the index of the maximum element
}
cout<<endl;
}
return 0;
}

OUTPUT:

C:\Users\uma mahesh\Desktop\per.exe 4 2 2 3 14 2 4 13 5 3 5 3 2 4 10 11 5 4 3 2 Process returned @ (exe) Press any key to continue. execution time : 2.697 s