Problem Solving►UVa

UVa 130 - Roman Roulette

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

Solution

直接模擬，看哪個起點可以讓 Josephus 活下來。
每次殺掉的位置會再從另一個位置補一個人進去，只需要記 Josephus 現在到哪了。

Code

UVa 130
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<cstdio>
#define N 101

bool live[N];
inline int getNext(int now, int n);
int main()
{
    int n, k;
    while (scanf("%d%d", &n, &k) && n)
    {
        int start, i, pos;

        for (start = 1; start <= n; start++)
        {
            for (i = 0; i <= n; i++)
                live[i] = true;

            int now = start;
            bool flag = true;
            pos = 1;

            for (i = 1; i < n&&flag; i++)
            {
                int count = k;
                while (count)
                {
                    count--;
                    if (!count)
                    {
                        int temp = now;
                        
                        live[now] = false;

                        if (now == pos)//將Josephus殺掉了
                        {
                            flag = false;
                            break;
                        }

                        //找人去埋，並換去剛殺的位子
                        for (int j = 0; j < k; j++)
                            temp = getNext(temp, n);

                        //如果有移動到Josephus 
                        if (temp == pos)
                            pos = now;
                        
                        live[now] = true;
                        live[temp] = false;
                    }

                    now = getNext(now, n);
                }
            }

            //Josephus還活著
            if (live[pos])
                break;
        }

        printf("%d\n", start);
    }

    return 0;
}
int getNext(int now, int n)
{
    do
    {
        now++;
        if (now > n)
            now = 1;
    } while (!live[now]);

    return now;
}