当前位置：首页 > news >正文

UVa 151 Power Crisis

news 2026/3/27 5:59:02

题目描述

在新西兰的这次电力危机中，政府制定了一个公平的停电方案。国家被划分为NNN个区域（奥克兰是区域111，惠灵顿是区域131313）。随机选择一个数字mmm，首先关闭区域111的电力，然后每隔mmm个区域关闭一个，循环进行直到所有区域都被关闭。例如，当N=17N = 17N=17，m=5m = 5m=5时，关闭顺序为：1,6,11,16,5,12,2,9,17,10,4,15,14,3,8,13,71,6,11,16,5,12,2,9,17,10,4,15,14,3,8,13,71,6,11,16,5,12,2,9,17,10,4,15,14,3,8,13,7。

问题是：惠灵顿（区域131313）应该最后一个被关闭（因为那里是电力总部所在地）。对于给定的NNN，需要找到一个最小的mmm，使得区域131313成为最后一个被选中的区域。

输入格式

输入包含多行，每行有一个整数NNN（13≤N<10013 \leq N < 10013≤N<100），以000作为输入结束标志。

输出格式

对于每个输入的NNN，输出对应的最小mmm值。

样例分析

输入：

17 0

输出：

题目分析与解题思路

问题本质

这是一个经典的约瑟夫环（Josephus Problem\texttt{Josephus Problem}Josephus Problem）变体问题。在原约瑟夫问题中，从第一个人开始报数，数到mmm的人出局，然后从下一个人继续报数。本题与标准约瑟夫问题的区别在于：

标准约瑟夫问题从第111个人开始数111，数到mmm的人出局；本题中，第一个被关闭的区域固定为111号区域
本题要求区域131313必须是最后一个被选中的区域
需要找到满足条件的最小mmm

约瑟夫环问题回顾

在经典约瑟夫环问题中，有nnn个人（编号000到n−1n-1n−1），每次数到mmm的人出局，下一个从出局者的下一位开始重新计数。最后幸存者的编号可以通过递推公式求解：
f(1)=0 f(1) = 0f(1)=0
f(i)=(f(i−1)+m)%i,其中 i≥2 f(i) = (f(i-1) + m) \% i, \quad 其中 \; i \geq 2f(i)=(f(i−1)+m)%i,其中i≥2

f(n)f(n)f(n)表示在nnn个人的情况下，最后幸存者的编号（从000开始编号）。

问题转换

由于第一个被关闭的区域固定为111号区域，我们可以重新定义编号：将111号区域视为000号，222号区域视为111号，以此类推。那么区域131313对应新编号中的121212号（因为13−1=1213 - 1 = 1213−1=12）。

在新的编号系统中：

初始位置：第一个被关闭的是000号
每次步长为mmm（跳过m−1m-1m−1个未关闭的区域，关闭第mmm个）
要求最后一个被关闭的区域是121212号

解题思路

对于每个mmm值，模拟关闭过程，检查区域131313是否为最后一个被关闭的区域。由于N<100N < 100N<100，我们可以枚举mmm从111开始递增，直到找到满足条件的最小mmm。

模拟步骤：

初始化一个数组region[0..n−1]\texttt{region}[0..n-1]region[0..n−1]，存储区域编号111到nnn
当前指针指向000号（即111号区域）
当剩余区域数量>1> 1>1时：
- 如果当前区域编号为131313（即region[blacked]==13\texttt{region[blacked]} == 13region[blacked]==13），则说明131313号区域不是最后一个被关闭的，当前mmm不满足条件
- 否则，将当前区域标记为已关闭，剩余区域数量减111
- 移动指针到下一个位置：先移动到下一个位置（(blacked + 1) % n\texttt{(blacked + 1) \% n}(blacked + 1) % n），然后从这个位置开始数mmm个未关闭的区域
当循环结束时，检查剩余最后一个区域是否是131313号

代码实现分析

代码使用了两层循环：

外层循环枚举mmm从111开始递增
内层循环模拟关闭过程

关键函数：

findCW\texttt{findCW}findCW：从当前位置开始，顺时针方向找到第count\texttt{count}count个未关闭的区域
findRegion\texttt{findRegion}findRegion：查找最后剩余的区域编号

算法复杂度

对于每个NNN，最坏情况下需要枚举mmm直到找到解。每次模拟过程的时间复杂度为O(N×m)O(N \times m)O(N×m)，但由于N<100N < 100N<100，即使枚举到较大的mmm也能在可接受时间内完成。

优化思路

可以利用约瑟夫环的递推公式进行优化。设J(n)J(n)J(n)为最后幸存者的新编号，则有：
J(1)=0 J(1) = 0J(1)=0
J(i)=(J(i−1)+m)%i,i≥2 J(i) = (J(i-1) + m) \% i, \quad i \geq 2J(i)=(J(i−1)+m)%i,i≥2

我们需要找到最小的mmm，使得J(N)=12J(N) = 12J(N)=12（对应原编号131313）。这样无需模拟，直接计算即可。

参考代码

// Power Crisis// UVa ID: 151// Verdict: Accepted// Submission Date: 2016-02-02// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intn,region[101];intfindCW(intindex,intcount){for(inti=index;i<n;i++)if(region[i]>0&&((--count)==0))returni;while(true){for(inti=0;i<n;i++)if(region[i]>0&&((--count)==0))returni;}}intfindRegion(){for(inti=0;i<n;i++)if(region[i]>0)returnregion[i];}intmain(){while(cin>>n,n){intm=0;while(true){for(inti=1;i<=n;i++)region[i-1]=i;inttotal=n,blacked=0;boolfound=true;m++;while(total>1){if(region[blacked]==13){found=false;break;}region[blacked]=0;total--;blacked=(blacked+1)%n;blacked=findCW(blacked,m);}if(found)break;}cout<<m<<endl;}return0;}