## Algorithm

Problem Name: beecrowd | 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 5 2 6 3 1234 233 Case 1: 3 Case 2: 1 Case 3: 25

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````

#include <stdio.h>
int josephusLoop(int n, int k, int startingPoint)
{
if(n == 1)
return 1;

int newSp, survivor;
newSp = (startingPoint + k - 2) % n + 1;
survivor = josephusLoop(n - 1, k, newSp);

if(survivor < newSp){
return survivor;
}else{
return survivor + 1;
}
}

int josephus(int n, int k)
{
return josephusLoop(n, k, 1);
}

int main()
{
int nc, n, k, s, i;
scanf("%i", &nc);

for (i = 1; i  < = nc; ++i)
{
scanf("%i %i", &n, &k);
s = josephus(n, k);
printf("Case %i: %in", i, s>;
}

return 0;
}
``````
Copy The Code &

Input

cmd
3 5 2 6 3 1234 233

Output

cmd
Case 1: 3 Case 2: 1 Case 3: 25

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````

#include <cstdio>
using namespace std;

int josephusLoop(int n, int k, int startingPoint)
{
if(n == 1)
return 1;

int newSp, survivor;
newSp = (startingPoint + k - 2) % n + 1;
survivor = josephusLoop(n - 1, k, newSp);

if(survivor < newSp){
return survivor;
}else{
return survivor + 1;
}
}

int josephus(int n, int k)
{
return josephusLoop(n, k, 1);
}

int main()
{
int nc, n, k, s;
scanf("%i", &nc);

for (int i = 1; i  < = nc; ++i)
{
scanf("%i %i", &n, &k);
s = josephus(n, k);
printf("Case %i: %in", i, s>;
}

return 0;
}
``````
Copy The Code &

Input

cmd
3 5 2 6 3 1234 233

Output

cmd
Case 1: 3 Case 2: 1 Case 3: 25

### #3 Code Example with Java Programming

```Code - Java Programming```

``````

import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

static FastScanner in = new FastScanner(System.in);
static PrintWriter out = new PrintWriter(System.out);

public static void main(String[] args) throws IOException {

int NC = in.nextInt(), n, k;
for (int i = 1; i  < = NC; i++) {
n = in.nextInt();
k = in.nextInt();
out.println("Case " + i + ": " + (josephus(n, k) + 1));
}
in.close();
out.close();
}

private static int josephus(int n, int k) {
// Runtime error :/
/* if (n == 1) {
return 0;
}
return (josephus(n - 1, m) + m) % n; */
int ans = 0;
for (int i = 2; i  < = n; i++) {
ans = (ans + k) % i;
}

return ans;
}

static class FastScanner implements Closeable {

private StringTokenizer tokenizer;

public FastScanner(InputStream input) {
tokenizer = new StringTokenizer("");
}

public String next() throws IOException {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
if (line == null) {
return null;
}
tokenizer = new StringTokenizer(line);
}
}

public int nextInt() throws IOException {
return Integer.parseInt(next());
}

public long nextLong() throws IOException {
return Long.parseLong(next());
}

public float nextFloat() throws IOException {
return Float.parseFloat(next());
}

public double nextDouble() throws IOException {
return Double.parseDouble(next());
}

@Override
public void close() throws IOException {
tokenizer = null;
}
}
}
``````
Copy The Code &

Input

cmd
3 5 2 6 3 1234 233

Output

cmd
Case 1: 3 Case 2: 1 Case 3: 25