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.

Note that you can use the following partial code.

#include <stdio.h>
#include <stdlib.h>
#include "function.h"

man* createList(int n){
    
    int i;
    man* curr;
    head = (man*)malloc(sizeof(man));
    curr = head;
    curr->id = 1;
    for(i=2; i<=n; i++){
        curr->next = (man*)malloc(sizeof(man));
        curr->next->prev = curr;
        curr = curr->next;
        curr->id = i;
    }
    curr->next = head;
    head->prev = curr;

    return head;
}


int solveJosephus(int step){

}

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

11345.c

Partial Judge Header

11345.h

Tags

Discuss

Description

輸入兩個向量，計算向量內積值。
兩個向量的內積，是各項相乘然後加總。例如 [1,2,3] 和 [4,5,6] 內積是 1*4+2*5+3*6 = 32
我們考慮高維度的稀疏向量，也就是大多數的元素都是零，只有少數不為零。資料的表示方式如下
dim1: value1 dim2: value2 dim3:value3 … 0:0
最後以 0:0 結束。例如
向量 [0,5,0,0,9,0,0,33] 是一個 8 維向量，可表示成
2:5 5:9 8:33 0:0
值為0 的維度都可以忽略不需描述，只需記錄非零的維度。利用上述的表示法，讀取兩個向量，然後算出它們的內積。

Input

輸入兩行，分別對應到兩個整數向量。
向量維度最高不超過 2 的 31 次方。記憶體用量不超過 32 MB。每一行都是以 0:0 結束

Output

內積值
最後記得換行

Sample Input  Download

Sample Output  Download

Tags

Discuss