新约瑟夫环

NC15595. 新约瑟夫环

描述

讲一个比较有意思的故事：约瑟夫是犹太军队的一个将军，在反抗罗马的起义中，他所率领的军队被击溃，只剩下残余的部队40余人，他们都是宁死不屈的人，所以不愿投降做叛徒。一群人表决说要死，所以用一种策略来先后杀死所有人。于是约瑟夫建议：每次由其他两人一起杀死一个人，而被杀的人的先后顺序是由抽签决定的，约瑟夫有预谋地抽到了最后一签，在杀了除了他和剩余那个人之外的最后一人，他劝服了另外一个没死的人投降了罗马。我们这个规则是这么定的：

在一间房间总共有n个人（编号0～n-1），只能有最后一个人活命。

按照顺时针的顺序时，编号就是从小到大的。

按照如下规则去杀人：

• 所有人围成一圈

• 顺时针(或逆时针)从1开始报数，每次报到q的人将被杀掉(顺时针逆时针交替进行，默认先进行顺时针)

• 被杀掉的人将从房间内被移走

• 然后从新方向上的下一个人开始重新报数，报到q的被杀掉，直到剩余一人

你要做的是：当你在这一群人之间时，你必须选择一个位置以使得你变成那剩余的最后一人，也就是活下来。

输入描述

在第一行中输入2个正整数n、q（0 ＜ n，q ≤ 1000），以空格分隔

输出描述

在一行输出最后活下来的人编号.

示例1

输入:

5 2

输出:

说明:

第一轮：[0,1,2,3,4]，从编号0开始往右，1号出局
第二轮：[0,2,3,4]，从编号2开始往左，0号出局
第三轮：[2,3,4]，从编号2开始往右，3号出局
第四轮：[2,4]，从编号4开始往左，2号出局。4号是最后一个人

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 476K, 提交时间: 2020-06-09 07:56:55

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 1000
using namespace std;
int n,m,lst[N+5],nxt[N+5];
I void Walk(int& p,int *s,int *s_)
{
	for(RI i=2;i<=m;++i) p=s[p];s[s_[p]]=s[p],s_[s[p]]=s_[p],p=nxt[p];
}
int main()
{
	RI i;for(scanf("%d%d",&n,&m),i=1;i<=n;++i) lst[i]=i-1,nxt[i]=i+1;lst[1]=n,nxt[n]=1;
	RI p=1;for(i=1;i^n;++i) i&1?Walk(p,nxt,lst):Walk(p,lst,nxt);return printf("%d\n",p-1),0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 448K, 提交时间: 2022-05-17 14:52:27

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define cir(x,i,n) ((x+i-1)%n+1)

int dfs(int n,int m,int k)
{
	int res=cir(1,n+k*(m-1)%n,n);
	if(n==1) return res;
	return cir(dfs(n-1,m,-k),res,n);
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n,m;
	cin>>n>>m;
	int ans=dfs(n,m,1);
	cout<<ans-1<<endl;
	return 0;
}

Python3 解法, 执行用时: 43ms, 内存消耗: 4564K, 提交时间: 2022-01-26 03:05:14

import collections
n,q=map(int,input().split())
d=collections.deque(range(0,n))
i=0
q-=1
while len(d)!=1:
    i+=1
    d.rotate(-q if i&1else q)
    d.popleft()
print(d[0])