Monk and Chamber of Secrets

QUESTION

Hagrid says \”follow the spiders\” and so Harry and Ron head to the Forbidden Forest. There they meet Aragog, a giant spider who tells them about the innocence of Hagrid. But Aragog only allows Hagrid to go back. These boys have got into a serious trouble now.\n\nThe only way to escape as Aragog says is to answer a question. \n\nAragog shows them a queue of N spiders of which only X spiders are to be selected. Each spider has some power associated with it. There are X iterations on the queue.\n\nIn each iteration, X spiders are dequeued (if queue has less than X entries, all of them will be dequeued) and the one with maximum power is selected and remaining spiders are enqueued back to the queue (in the order they were dequeued) but their power is decreased by one unit. If there are multiple spiders with maximum power in those dequeued spiders, the one which comes first in the queue is selected. If at any moment , power of any spider becomes 0, it can’t be decremented any further, it remains the same.\n\nNow, Aragog asks the boys to tell him the positions of all the selected spiders (positions in the initial given queue) in the order they are selected. As the boys are frightened and can’t think of anything , they call Monk for the rescue. Help Monk to get the answer fast and save the boys.\n\nInput Format:\nThe first two values represent the integers N and X, denoting the number of spiders in the queue and the number of spiders that have to be selected respectively.\n\nThe values followed by it consists of an array A,A[i] denoting the power of spider at position i (1 less than equal to i less than equal to N)\n\n\nOutput Format:\nFor each of the X iterations, output the position of the selected spider in that iteration. Position refers to the index at which the spider was present in the initial given queue (1 based indexing).

“TESTCASE_1”: “7 3 1 5 6 2 2 3 4\n###—###SEPERATOR—###—\n3 6 7”, “TESTCASE_2”: “5 5 1 2 3 4 5\n###—###SEPERATOR—###—\n5 4 3 1 2”, “TESTCASE_3”: “3 1 1 5 7\n###—###SEPERATOR—###—\n1”, “TESTCASE_4”: “6 5 1 2 2 3 4 5\n###—###SEPERATOR—###—\n5 6 4 1 2”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<string.h>
 
int main()
{
    int idx,l,n,flag,y,x,d[1000],e[1000],max,c[100010],a[100010],i,j;
    scanf("%d%d",&n,&x);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        c[i]=i;
    }
    for(j=1;j<=x;j++)
    {
        max=-1;
        if(n<x)
            y=n;
        else
            y=x;
        for(i=1;i<=y;i++)
            if(a[i]>max)
            {
                max=a[i];
                idx=c[i];
            }
        flag=0;
        for(i=1;i<=x;i++)
        {
            if(idx==c[i])
            {
                flag=1;
                continue;
            }
            if(a[i]>0)
                d[i-flag]=a[i]-1;
            else
                d[i-flag]=a[i];
            e[i-flag]=c[i];
        }
        for(i=1;i<=n-x;i++)
        {
            a[i]=a[i+x];
            c[i]=c[i+x];
        }
        l=1;
        for(;i<n;i++)
        {
            a[i]=d[l];
            c[i]=e[l++];
        }
        n--;
        printf("%d ",idx);
    }
    printf("\n");
    return 0;
}

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.