Problem 1: Circular Elimination

Points:

Small Case: 10 Answer: 106

Large Case: 20 Answer: 88999997

N numbers (1 to N) are arranged in a circular fashion. Starting from kth(<N), every second number is eliminated from the circle. You need to determine the xth(<N) number which is removed.

Small Case, N=1000, x=555, k=888.
large case, N=999999999, x=55555, k=88888888.

Solution:

This problem is commonly known as Extended Josephus Problem
The Reursive formula for the case when counting starts from 1 is given by:

J(n,x) = 1, if n=1 and x=1
         2, if n>1 and x=1
         1, if n,z>1 and J(n-1,x-1)=n-1
         J(n-1,x-1)+2, if J(n-1,x-1)<=n-2

Now, for the case when counting starts from k, we just shift kth value to 1st, and find kth number in circle.

Reference: Armin Shams-Baragh, Formulating The Extended Josephus Problem

Code:

#include <stdio.h>

long long Josephus(long long n, long long x)
{
  if(n==1 && x==1)
    return 1;
  if(n>1 && x==1)
    return 2;
  long long res = Josephus(n-1,x-1);
  if(res==(n-1))
    return 1;
  if(res <= n-2)
    return res+2;  
}

int main()
{
  long long n,x,k,res;
  scanf("%lld%lld%lld",&n,&x,&k);
  res = Josephus(n,x)+k-1;
  printf("%lld\n",res>n?res-n:res);
}