HackerEarth Round Table Killers problem solution

In this HackerEarth Round Table Killers problem solution There is a round table in which N people are sitting. You can look at the image for their seating arrangement. Initially, the person numbered X holds a gun. In addition to it there is a special number K that helps in determining the persons to be killed. The killing starts as follows – Firstly the person numbered X starts and he kills a total of X%X people sitting clockwise of him and he gives the gun to the person i who is sitting just next to the last person killed. Now that person also kills the next i%K people and this goes on. If at any instant the total number of persons that are remaining is not greater than i%K where i is the number of people holding the gun then the person i wins. You can show that sooner or later only one person remains. So your job is to decide which numbered person will win this killing game.

HackerEarth Round Table Killers problem solution.

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define reset(a) memset(a,0,sizeof(a))
#define rep(i,j,k) for(i=j;i<=k;++i)
#define per(i,j,k) for(i=j;i>=k;--i)
#define print(a,start,end) for(i=start;i<=end;++i) cout<<a[i];
#define endl "n"
#define inf 100000000000000
LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
set<int> s;
int main()
  {
    //ios_base::sync_with_stdio(0);
    int n , k , temp , x;
    cin >> n >> k >> x;
    for(int i = 1 ; i <= n ; i++)
      s.insert(i);
    int offset = n%k;

    set<int>:: iterator it;
    while(1)
      {
        offset = x%k;
        temp = x;
        s.erase(temp);  
        if(offset + 1 > s.size())
          {
            cout << x ;
            return 0;
          }
        while(offset)
          {
            it = s.upper_bound(x);
            if(it == s.end())
              {
                x = *(s.begin());
                s.erase(s.begin()); 
                --offset;
              } 
            else
              {
                x = *it;
                s.erase(it);
                --offset;
              } 
          }
        it = s.upper_bound(x);
        if(it == s.end())
          {
            x = *s.begin();           
          }
        else
            x = *it;
        s.insert(temp);
      }
  }

HackerEarth Round Table Killers problem solution.

Leave a Reply