CPD-Exercise 6 solved

In this exercise, you will need to write a program to implement a circular linked list to solve the Josephus problem.

Assuming that there are n people and each person has its own name. They will stand in a circle (i.e., the first people and the last people is connected) and they will face a terrible elimination game. They will be killed in the specific order until there is only one person remain. We will give you the value k for the number of the step, which means the required number of steps that we need to move for killing a person each time. What’s more, we will give you the direction of the elimination (i.e., clockwise or counter clockwise).


Here is a simple example in which there are five people in the circle (n = 5),  k = 2, and direction = CLOCKWISE

Alan

(start from here)
Bob

(1 step)
Cindy

(2 step)
Danny
Eve
We will start this game from the first people (Alan), and then we will move 2 steps to kill Cindy.  

Alan

(2 step)
Bob
Cindy

(killed)
Danny

(new start position)
Eve

(1step)
After removing (i.e., killing) Cindy, the new position to start will be Danny. Then, we move 2 steps to kill Alan.  

Alan

(killed)
Bob

(new start position)
Cindy

(killed)
Danny

(1step)
Eve

(2 step)
After removing to kill Eve.
Alan, the new start position will be Bob. Again, we then move 2 steps
Alan

(killed)
Bob

(new start position) 

(2 step)
Cindy

(killed)
Danny

(1step)
Eve

(killed)
After removing Eve, the new start position will be Bob because Alan was removed. Then we move 2 steps and kill Bob. Finally, Danny is the final surviver in this game and the game will be stopped.  

 

If the direction is counter clockwise, the situation will be:

Alan

(start from here)
Bob

 
Cindy

(new start position)
Danny

(2 step -> killed)
Eve

(1 step)
The game still start from the first people (i.e., Alan), and the only different thing is that we kill people in a counter-clockwise order.  

 

In this Exercise, your task is to print the order of people killed in the format <NAME> 

KILLED.  If there is only one person left, please print out <SURVIVER_NAME> SURVIVE.  Notice: you must use a linked-list to solve this exercise. Otherwise, you will get no score.

 

The table below shows the example input and output. The integer of the first input (e.g., 10 in the first example) represents the numbers of people n. The next line of input represents the list of peoples’ names in the circle. There are two parameters in the last line of input. The first parameter represents how many steps to move (i.e., the

value of k) and the direction of the elimination (CLOCKWISE or

COUNTERCLOCKWISE).

 

Input 
Output 
10 

AA BB CC DD EE FF GG HH II JJ 

2 CLOCKWISE 
CC KILLED 

FF KILLED 

II KILLED 

BB KILLED 

GG KILLED 

AA KILLED 

HH KILLED 

EE KILLED 

JJ KILLED 

DD SURVIVE 
4 

LUNE FOODPAPA KENN LYON 

3 COUNTERCLOCKWISE 
FOODPAPA KILLED 

LUNE KILLED 

KENN KILLED 

LYON SURVIVE