Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- using namespace std;
- int N, K, X;
- int re_arrange(int x);
- bool inrange(int x);
- int main(){
- cin >> N >> K >> X;
- int n_alive = N; //number of alive people.
- int kill_count, victim_idx, status[N+1];
- fill_n(status, N+1, 1);
- 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 ..."
- {
- kill_count = 0; //will keep the count of the number of victims
- victim_idx = X + 1; //"he gives gun to the person who is sitting just next ..."
- victim_idx = re_arrange(victim_idx); //check if victim_idx is within range
- while(kill_count < X%K) //keep on killing until we reach the needed kill count (X%K)
- {
- if(status[victim_idx]) //if the victim is alive ... kill it and increase kill_count
- {
- status[victim_idx] = 0;
- kill_count++;
- }
- victim_idx++; //in all cases, increase victim_idx and check if within range
- victim_idx = re_arrange(victim_idx);
- }
- n_alive -= kill_count; //update number of people alive to take into account kill_count
- 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)
- {
- victim_idx++;
- victim_idx = re_arrange(victim_idx);
- }
- X = victim_idx;
- }
- cout << X;
- return 0;
- }
- bool inrange(int x) {
- if (x >= 1 && x <= N)
- return true;
- else
- return false;
- }
- int re_arrange(int x) {
- if (!inrange(x)) {
- x %= N;
- if (x == 0)
- return 1;
- }
- return x;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement