Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1030
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1030
Flavious Josephus Legend
By Neilor Tonin, URI 
Brazil
Timelimit: 1
The Josephus' problem is known because of the Flavius Josephus' legend, a Jewish historian living in the 1st century. According to Josephus' account of the siege of Yodfat, he and his 40 comrade soldiers were trapped in a cave, the exit of which one was blocked by Romans. They chose suicide over capture and decided that they would form a circle and start killing themselves skipping three in three. Josephus says that, by luck or maybe by the hand of God, he remained the last and gave up to the Romans.”
Input
There are NC (1 ≤ NC ≤ 30 ) test cases. In each input test case there will be a pair of positive integer numbers n (1 ≤ n ≤ 10000 ) and k (1 ≤ k ≤ 1000). The number n represents the quantity of people in the circle, numbered from 1 to n. The number k represents the size of step between two men in the circle.
Follow an example with 5 men and step 2: In this example the remaining element is 3.
The data must be read from standard input.
Output
For each test case we will have an output line, presenting in the following format: Case n: m always with a space before n and m.
| Output Sample | Input Sample |
|
3 |
Case 1: 3 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include<stdio.h>
int josephus(int n,int k);
int main()
{
int tcase,n,k,i;
while(scanf("%d",&tcase) == 1){
for(i = 1; i < = tcase; i++){
scanf("%d %d",&n,&k);
int tmp = josephus(n,k);
printf("Case %d: %d\n",i,tmp);
}
}
return 0;
}
int josephus(int n,int k)
{
if(n == 1)
return 1;
else
return (josephus(n-1,k)+k-1)%n+1;
}
Input
5 2
6 3
1234 233
Output
Case 2: 1
Case 3: 25
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <stdio.h>
#include <cstring>
int flavious(int x, int y){
if(x == 1) return 0;
return (flavious(x-1,y)+y)%x;
}
int remaining(int n, int k) {
int r = 0;
for (int i = 2; i <= n; i++)
r = (r + k) % i;
return r;
}
int main(){
int n, x, y, j, num, pulo;
scanf("%d",&n);
for(int i = 0; i < n; i++){
scanf("%d %d",&x,&y);
//printf("Case %d: %d\n",i+1,flavious(x,y)+1);
printf("Case %d: %d\n",i+1,remaining(x,y)+1>;
}
return 0;
}
Input
5 2
6 3
1234 233
Output
Case 2: 1
Case 3: 25
#3 Code Example with Java Programming
Code -
Java Programming
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner obj=new Scanner(System.in);
int testcase=obj.nextInt();
for (int k=1;k < testcase+1;k++)
{
int n = obj.nextInt();
int m = obj.nextInt();
Queue < Integer> queue = new LinkedList(); //queue of integer type used
for (int i = 1; i < = n; i++)
queue.add(i); //adding value to queue
int a=0;
while (!queue.isEmpty()) // removing particular element untill queue become empty
{
for (int i = 0; i < m-1; i++)
queue.add(queue.remove());
a=queue.remove();
}
System.out.println("Case "+k+": "+a);
}
}
}
Input
5 2
6 3
1234 233
Output
Case 2: 1
Case 3: 25
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const { readFileSync } = require("node:fs")
const [[numLines], ...input] = readFileSync("/dev/stdin", "utf8")
.split("\n", 31)
.map((line) => line.split(" ", 2).map((value) => Number.parseInt(value, 10)))
const Josephus = {
/**
* @param {number} n
* @param {number} k
* @returns {number}
*/
lastIndex(n, k) {
if (n <= 0) return null
else if (n == 1) return 0
else if (k == 1) return n - 1
else if (k == 2) return 2 * (n - 2 ** Math.floor(Math.log2(n)))
else if (k > n) return (Josephus.lastIndex(n - 1, k) + k) % n
let res = Josephus.lastIndex(n - Math.floor(n / k), k) - (n % k)
if (res < 0) res += n
else res += Math.floor(res / (k - 1))
return Math.floor(res)
}
}
function main() {
const output = Array.from({ length: numLines }, (_, index) => {
const [N, K] = input[index]
return `Case ${index + 1}: ${Josephus.lastIndex(N, K) + 1}`
})
console.log(output.join("\n"))
}
main()
Input
5 2
6 3
1234 233
Output
Case 2: 1
Case 3: 25
#5 Code Example with Javascript Programming
Code -
Javascript Programming
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var lines = input.split('\n');
var prompt = function(texto) { return lines.shift();};
const cases = parseInt(prompt());
for (let j = 1; j < = cases; j++) {
var [num, step] = prompt().split(" ").map(Number);
var people = [];
var counter = -1;
for (let i = 1; i < = num; i++) {
people.push(i);
}
while (people.length > 1) {
for (let i = 0; i < step; i++) {
counter++;
if (counter >= people.length) {
counter = 0;
}
}
people.splice(counter, 1);
counter--;
}
console.log(`Case ${j}: ${people[0]}`);
}
Input
5 2
6 3
1234 233
Output
Case 2: 1
Case 3: 25
#6 Code Example with Python Programming
Code -
Python Programming
for g in range(int(input())):
n, k = [int(x) for x in input().split()]
v = [1 for x in range(1, n+1)]
m = 0
i = p = 1
while (m < n-1):
if v[i] == 1: p += 1
if p == k:
v[i] = 0
m += 1
p = 0
i += 1
if i == n: i = 0
i = 0
while v[i] == 0: i += 1
print('Case {}: {}'.format(g+1, i+1))
Input
5 2
6 3
1234 233
Output
Case 2: 1
Case 3: 25