CE20201A Editorial

PROBLEM LINK:

Contest Link:
https://www.codechef.com/CE12020/problems/CE20201A
Practice:
https://www.codechef.com/problems/CE20201A

Author : nash_057 [https://www.codechef.com/nash_057 ]
Tester: shanvid [https://www.codechef.com/shanvid ]
Editorialist: shanvid [https://www.codechef.com/shanvid ]

DIFFICULTY: EASY

PREREQUISITES:

Basic Maths, Any programming language

PROBLEM:

In a party, friends decided to play a game called Elimination Circle. In this ‘n’ people were made to sit in a circular manner. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is eliminated from the game. The elimination proceeds around the circle (which is becoming smaller and smaller as the people are removed), until only the last person remains, who is the winner. Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is removed from the circle. The task is to choose the place in the initial circle so that you are the last one remaining and thus win the game.

EXPLANATION:

Input:

  • First line will contain NN, number of People.
  • Second line K, shows total skipped

Output:

Output is a single integer number showing the calculated start position.

Constraints

  • 1≤N≤1061≤N≤106
  • 1≤K≤1061≤K≤106

Sample Input:

    5
    2

Sample Output:

    3

EXPLANATION:

Firstly, the person at position 2 is removed, then person at position 4 , then person at position 1 is removed. Finally, the person at position 5 is elimiated. So the person at position 3 wins.

SOLUTIONS:

#include
using namespace std;
int exclusion(int n, int k);

int main()
{
int T;
cin>>T;
while(T–)
{ int n,k;
cin>>n;
cin>>k;
cout << exclusion(n, k);
}
return 0;
}

int exclusion(int n, int k)
{
if (n==1)
{
return 1;
}
else
{
return (exclusion(n - 1,k) + k-1) % n + 1;
}
}