说明

该程序模拟了“Eeny Meeny”部落的酋长选举过程，用于找出在给定人数范围内无论计数方向如何都不会被选为酋长的“安全位置”。程序通过约瑟夫问题的变种来解决这一选举机制，并输出最接近特定位置的安全位置或提示需要更精确的估计。

算法标签

• 约瑟夫问题
• 模拟
• 数学计算

解题思路

1. 问题分析：选举过程类似于约瑟夫问题，参与者围成一圈，按照特定规则（每念到o!时淘汰一人）逐步淘汰，直到只剩一人。需要找出在给定人数范围内不会被选为酋长的位置。
2. 约瑟夫问题预处理：使用动态规划预先计算不同人数时的幸存者位置。
3. 输入处理：读取人数范围，处理到0 0结束。
4. 安全位置判断：在给定范围内检查是否存在一个位置，该位置在所有可能的人数情况下都不会成为幸存者。
5. 输出结果：根据判断结果输出安全位置或提示需要更精确的估计。

分析

• 约瑟夫问题：通过递推公式a[n] = (a[n - 1] + K) % n计算幸存者位置，其中K为淘汰步长（此处为15）。
• 安全位置：对于给定范围[low, high]，检查是否存在一个位置k，使得对于所有n在[low, high]内，k不是幸存者。
• 结果判断：如果在范围内存在这样的k，则输出最小的k；否则提示需要更精确的估计。

实现步骤

1. 预处理约瑟夫问题：使用动态规划计算a[n]，表示n人时的幸存者位置。
2. 输入处理：循环读取人数范围low和high，直到0 0。
3. 安全位置检查：
   • 对于每个n在[low, high]内，计算幸存者位置t。
   • 标记所有可能的幸存者位置。
   • 检查是否存在未被标记的位置k（即安全位置）。
4. 输出结果：根据检查结果输出安全位置或提示。

代码解释

• 预处理：a数组存储不同人数时的幸存者位置，通过递推公式计算。
• 输入处理：读取low和high，确保low <= high。
• 安全位置标记：b数组标记在给定范围内所有可能的幸存者位置。
• 结果判断：遍历可能的k值，检查是否存在未被标记的安全位置。
• 输出：根据检查结果输出相应的信息。

该程序通过高效的预处理和检查，快速确定安全位置或提示需要更精确的估计，适用于解决类似约瑟夫问题的选举机制。

代码：

/* POJ1212 HDU1650 UVA180 LA5240 Eeny Meeny */

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int K = 15;
const int N = 1e6;
int a[N + 1], b[N + 1];

int main()
{
    a[0] = a[1] = 0;
    for(int n = 2; n <= N; n++)
        a[n] = (a[n - 1] + K) % n;

    int low, high;
    while(~scanf("%d%d", &low, &high)) {
        if(low > high) swap(low, high);

         if(low == 0 && high == 0) break;

        memset(b, 0, sizeof(b));
        for(int i = low; i <= high; i++) {
            int t = a[i];
            if(t > i / 2) t = i - t;
            if(t < low / 2) b[t] = 1;
        }

        bool flag = false;
        int k = 1;
        for(k = 1; k < low / 2; k++)
            if(b[k] == 0) {
                flag = true;
                break;
            }

        if(flag) printf("%d\n", k);
        else printf("Better estimate needed\n");
    }

    return 0;
}