Advertisement
Guest User

Ayoub - Roundtable Killers Problem

a guest
Jan 19th, 2018
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.79 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. int N, K, X;
  6. int re_arrange(int x);
  7. bool inrange(int x);
  8.  
  9. int main(){
  10.     cin >> N >> K >> X;
  11.     int n_alive = N;  //number of alive people.
  12.     int kill_count, victim_idx, status[N+1];
  13.     fill_n(status, N+1, 1);
  14.     while(n_alive > X%K) //"If at any instant the total persons that are remaining is not greater than i%K, person i is the winner ..."
  15.     {
  16.         kill_count = 0;    //will keep the count of the number of victims
  17.         victim_idx = X + 1; //"he gives gun to the person who is sitting just next ..."
  18.         victim_idx = re_arrange(victim_idx); //check if victim_idx is within range
  19.  
  20.         while(kill_count < X%K)    //keep on killing until we reach the needed kill count (X%K)
  21.         {
  22.             if(status[victim_idx])  //if the victim is alive ... kill it and increase kill_count
  23.             {
  24.                 status[victim_idx] = 0;
  25.                 kill_count++;
  26.             }
  27.             victim_idx++;       //in all cases, increase victim_idx and check if within range
  28.             victim_idx = re_arrange(victim_idx);
  29.         }
  30.  
  31.         n_alive -= kill_count; //update number of people alive to take into account kill_count
  32.  
  33.         while(!status[victim_idx]) //gun is given to people on the left of next victim ... so we look for next living person to the left of last victim (victim_idx)
  34.         {
  35.             victim_idx++;
  36.             victim_idx = re_arrange(victim_idx);
  37.         }
  38.         X = victim_idx;
  39.     }
  40.     cout << X;
  41.     return 0;
  42. }
  43.  
  44.  
  45. bool inrange(int x) {
  46.     if (x >= 1 && x <= N)
  47.         return true;
  48.     else
  49.         return false;
  50. }
  51.  
  52. int re_arrange(int x) {
  53.     if (!inrange(x)) {
  54.         x %= N;
  55.  
  56.         if (x == 0)
  57.             return 1;
  58.     }
  59.  
  60.     return x;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement