Description

Based on the original Josephus Problem introduced in class, an additional rule of this problem is to change

direction of counting after killing a person.  For example, there are 8 people, numbered 1 to 8, in a circle

and arranged in clockwise.  The step to kill is 3. 

The sequence of killing people is

1, 2, 3 (kill 3, change the direction to counter-clockwise)

2, 1, 8 (kill 8, change the direction to clockwise)

1, 2, 4 (kill 4, change the direction to counter-clockwise)

2, 1, 7 (kill 7, change the direction to clockwise)

1, 2, 5 (kill 5, change the direction to counter-clockwise)

2, 1, 6 (kill 6, change the direction to clockwise)

1, 2, 1 (kill 1)

 

So the person numbered 2 is the survivor.

 

You're asked to solve this problem using circular linked list.

You will be provided with main.c and function.h, and you need to implement function.c.

 

Note there is a time limit to solve this problem: 3 seconds.

Input

The input has two integers, n and m, where n is the number of total people, and m is the step to kill.

Output

The output is an integer: the survivor's number.  There is a newline after that.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11335.c

Partial Judge Header

11335.h

Tags

Discuss

Description

This problem asks you：

1. To create a linked list to store a sequence of positive integers.
2. To delete some given integers in the linked list. If the node is not existing, do nothing.
3. To insert an integer into an appropriate position in the linked list.

 

For example, if the input is

1 2 3 4 5 6 7 -1

1 1 4 -1

2

1 8

3 9

The first sequence is 1 2 3 4 5 6 7 -1, so a linked list is created as

The second sequence is 1 1 4 -1, so do the follows.

 

After p1=1, the list becomes

because the first node is 1.

 

After p2 = 1, the list becomes

because the first node is 2.

 

After p3 = 4, the list becomes

because the fourth node is 6.

 

The next number is 2, so you need to read two lines.

 

The first line is 1 8, so the data of new node is 8 and should be inserted at position 1. The list becomes

 

The second line is 3 9, so the data of new node is 9 and should be inserted at position 3. The list becomes

 

Finally, the answer is 8 3 9 4 5 7.

 

Note for those who are not familiar with partial judge:

 

You will be provided with main.c and function.h, and asked to implement function.c containing three function createList, deleteNode and insertNode.

For OJ submission:

       Step 1. Submit only your function.c into the submission block. (Please choose c compiler)

       Step 2. Check the results and debug your program if necessary.

 

Input

The input contains 3 parts:

1.  A sequence of positive integers as the linked list, except the last one, which is -1.

2. A sequence of positive integers as the position need to be deleted, except the last one, which is -1.

3. A number N means the number of inserted node, and next N lines contain a pair of number (X, Y). X is the position which you are asked to insert a new node into and Y is the data of the node.

Output

The output contains the sequence of resulting linklist.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11336.c

Partial Judge Header

11336.h

Tags

Discuss