PROBLEM LINK:
Contest Link:
Practice:
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;
}
}