[URI ONLINE JUDGE] – 1030– Flavious Josephus Legend

The Josephus problem is this way 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 was blocked by Romans. They chose suicide over capture and decided that they would form a circle and start killing themselves using a step of three. Josephus states 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 represent 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 a line of output, presenting the in the following format: Case n: m always with a space before n and m.

Sample Input Sample Output
3
5 2
6 3
1234 233
Case 1: 3
Case 2: 1
Case 3: 25

my solution:


#include <iostream>
#include <vector>

using namespace std;

int josephus(int n, int k){
if (n == 1) return 1;
return ((josephus(n - 1, k) + k - 1) % n) + 1;
}

int main(){
unsigned int k, n;
int c, q;

cin >> q;
c = 0;
while (++c <= q){ cin >> n >> k;
cout << "Case " << c << ": " << josephus(n, k) << endl;
}

return 0;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s