首页 > 代码库 > UVA305 - Joseph(数论 + 打表)

UVA305 - Joseph(数论 + 打表)

UVA305 - Joseph(数论 + 打表)

题目链接

题目大意:约瑟夫环问题:n个人围成一圈,每次都淘汰第m个人,问最后一个幸存下来的人的编号。
这题的意思有点不一样,它规定前面的k个人是好人,后面的k个人是坏人(2 ? k形成环)。问最小的m是多少,可以先把后面的k个坏人淘汰再淘汰好人。

解题思路:这题有个递推式:ai = (ai - 1 + m - 1) % (2 ? k - (i - 1))
ai表示第i次淘汰的人的编号。后面取余的是剩下的人数。
注意这题的k仅仅可能有14种,可是測试的例子可能有非常多,所以要先将每种k的可能相应的值算出来保存下来。不然会超时。

代码:

#include <cstdio>
#include <cstring>

using namespace std;

const int N = 20;A

int solve (int k) {

    int n = 2 * k;
    int m = k + 1;
    int pre, cnt;
    while (1) {

        cnt = 1;
        pre = (m % n) == 0 ? n : m % n;
        while (cnt <= k) {
            if (pre <= k)
                break;
            pre = (pre + m - 1) % (n - cnt) == 0 ? (n - cnt) : (pre + m - 1) % (n - cnt); 
            cnt++;
        }

        if (cnt == k + 1)
            return m;
        else {

            if (m % n == 0)
                m += k + 1;
            else
                m++;
        }
    }
}

int main () {

    int k;
    int ans[N];
    for (int i = 1; i < 15; i++)
        ans[i] = solve(i);
    while (scanf ("%d", &k) && k) {
        printf ("%d\n", ans[k]);
    }
    return 0;
}

UVA305 - Joseph(数论 + 打表)