Problem Solving►UVa

UVa 13114 - Josephus lottery II

Contents

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

Problem

題目網址

給定 m ，學生繞成一圈，找出一個 k 使得所有學生經過剔除後(取小的)，最後剩下的位置為 m。
學生有 100 人從 1 ~ 100。

從 1 開始，順時針數 k 個，第 k 個移除，接著從順時針的下一個開始。
逆時針數第 k 個，移除，再來從逆時針的下一個開始順時針數。
如此順逆交替著做，直到剩下最後一人。

ex.
如果學生數為 10 人，k = 3，剔除的順序為: 3, 1, 4, 10, 5, 9, 6, 8, 7

Solution

因為 k 給定在 1~1000 ，直接暴力模擬 k 為 1~1000 時，最後剩下的是 x ，然後建表 ans[x] = k。
(記得 k 要取最小 和 index 的處理)

Morris 有用狀態壓縮什麼的加速，但我想我就到此為止了…

Code

UVa 13114
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
#include<cstdio>
#define N 100

int main()
{
    bool student[N];
    int ans[N] = {};
    int i;

    for (int k = 1; k <= 1000; k++)
    {
        for (i = 0; i < N; i++)
            student[i] = true;
        int now = 0;

        for (i = 1; i < N; i++)//跑99次
        {
            int count = k;

            while (count)
            {
                count--;
                if (!count)
                    student[now] = false;

                if (i & 1)
                    do
                    {
                    now++;
                    if (now == N)
                        now = 0;
                    } while (!student[now]);
                else
                    do
                    {
                    now--;
                    if (now < 0)
                        now = N - 1;
                    } while (!student[now]);
            }
        }

        for (i = 0; i < N; i++)
            if (student[i])
            {
            if (!ans[i])
                ans[i] = k;
            break;
            }
    }

    int m;
    while (scanf("%d", &m) && m)
        printf("%d\n", ans[m - 1]);

    return 0;
}