Wednesday 22 July 2015

DANGER


In Danger

Link to the question : DANGER 

HINT :

Josephus problem can be solved by using a circular queue but for k=2 we can derive a formula. First try solving by keeping number of people, n, equal to some power of 2, i.e, 4,8 etc. You will notice that the last to stay is at position 1. 
Hence we write  n = 2^m + t. Now, if t people are killed, the one with whom the cycle starts stays till the end. So, after killing t people, the cycle will start from the position 2*t - 1. Hence, you need to find that position.

RECOMMENDED QUESTION :

After getting an AC, try solving this question .

SOURCE CODE :

/* In Danger */

/* Sushant Gupta */



#include<stdio.h>

#include<math.h>

int main()

{

    char a[10];

    scanf("%s",a);



    while(1)

    {

        if(a[0]== '0' && a[1]== '0')

            return 0;



        long long int x;

        x = 10 * (a[0] - '0') + (a[1]- '0');

        x = x * pow(10, (a[3]- '0'));

        int m;

        m = log2(x);

        long long int n;

        n = pow(2,m);

        long long int ans;

        ans = 2*(x - n) + 1;

        printf("%lld\n",ans);

        scanf("%s",a);

    }



}

No comments:

Post a Comment