Light OJ 1179 – Joshephus Problem [solved]

Posted on March 4, 2019 by Mobarak Hosen Shakil — Leave a comment

Joshephus Problem is a very interesting mathematical problem. To solve this problem you have to think bottom to top approach. Since at the end there must be one alive, before then there was two alive. Result can be found through recursive formula:
for F(1, K) = 1;
for F(N, K) = (F(N-1, K) + K-1)%n+1; until n!= 1;
You can better understand Jeshephus Formula through this link: https://goo.gl/AkohGN

/******************************************
          Mobarak Hosen Shakil
        ICE, Islamic University
     ID: mhiceiuk(all), 29698(LOJ)
   E-mail: mhiceiuk @ (Gmail/Yahoo/FB)
 Blog: https://iuconvergent.wordpress.com
*******************************************/

#include<bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0)
#define LL long long int
#define ULL unsigned LL

const int inf=1<<30;
const LL INF=1e18;
const int MOD=1e9+7;

/// recursive formula
LL Solve(LL n, LL k)
{
    if(n==1)
        return 1;
    return ((Solve(n-1, k)+k-1)%n+1);
}


int main()
{
    int tn;
    scanf("%d", &tn);
    for(int cs=1; cs<=tn; cs++){
        LL n, k;
        scanf("%lld%lld", &n, &k);
        LL res=1;
        for(int i=2; i<=n; i++)
        {
            res = ((res+(k-1))%(LL)i)+1;       /// here i used an iterative approach 
        }
        printf("Case %d: %lld\n", cs, res);
        ///printf("Case %d: %lld\n", cs, Solve(n, k));
    }
    return 0;
}