http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1149
Josephus Problem
|
Accepted : 44 |
|
Submit : 334 |
Time Limit : 5000 MS |
|
Memory Limit : 65536 KB |
Josephus Problem
Do you know the famous Josephus Problem? There arenpeople standing in a circle waiting to be executed. The counting out begins at the first
people in the circle and proceeds around the circle in the counterclockwise direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as
the executed people are removed), until only the last person remains, who is given freedom.
In traditional Josephus Problem, the number of people skipped in each round is fixed, so it's easy to find the people executed in the i-th round. However, in this problem, the number of people skipped in each round
is generated by a pseudorandom number generator:
x[i+1] = (x[i] * A + B) % M.
Can you still find the people executed in the i-th round?
Input
There are multiple test cases.
The first line of each test cases contains six integers 2 ≤ n ≤ 100000, 0 ≤ m ≤ 100000, 0 ≤ x[1], A, B < M ≤ 100000. The second line contains m integers 1 ≤ q[i] < n.
Output
For each test case, output a line containing m integers, the people executed in the q[i]-th round.
Sample Input
2 1 0 1 2 3
1
41 5 1 1 0 2
1 2 3 4 40
Sample Output
1
2 4 6 8 35
#include<iostream>
#include<stdio.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int ans[100001];
int xw[100001];
const int maxn=200000;
int w,sum[maxn<<2];
void build(int l,int r,int rt){///建立线段树
sum[rt] = r - l + 1;
if(l == r) return ;
int m = (l+r) >> 1;
build(lson);
build(rson);
}
int update(int p,int l,int r,int rt){///更新单个节点
sum[rt]--;
if(l == r) return l ;
int m = (l + r) >> 1;
if(p <= sum[rt<<1])
return update(p,lson);
else
return update(p-sum[rt<<1],rson);
}
int main()
{
int n,m,i;
int x,A,B,M;
while(scanf("%d%d%d%d%d%d",&n,&m,&x,&A,&B,&M)!=EOF)
{
build(1,n,1);
int z = 1;
for(i = 1; i <= n; i++)
{
z = ((int)x+z)%sum[1];
if(z == 0) z = sum[1];
int s = update(z,1,n,1);
ans[i] = s;
x = (int)(((__int64)x * A + B) % M);
}
for(i = 0; i < m; i++)
scanf("%d",&xw[i]);
for(i=0;i<m-1;i++)
printf("%d ",ans[xw[i]]);
if(m!=0) printf("%d",ans[xw[m-1]]);
printf("\n");
}
return 0;
}
相关推荐
据说着名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1...
利用Java求解约瑟夫环问题,控制台程序
约瑟夫问题的求解方案,经典
约瑟夫环问题描述: 编号为123...n的人一词围成一圈,从第k个人开始报数(从1开始),数到m的人退出。接着下一个人又从1开始报数,数到m的人退出,以此类推。问:剩下的人的编号是多少?
约瑟夫环
Josephus
Super clear answer! With the Josephus problem
labview的josephus问题编程
用顺序表处理Josephus问题 c语言
Josephus问题的解答,分别使用不同的方法
Josephus的几种解法
用c++解决了josephus问题:有n个人围在一个圆桌周围,现从第s个人开始报数,数到第m个人又出列…如此反复直到所有的人全部出列为只止。
用链表法实现josephus,开发工具为C语言。
约瑟夫问题(Josephus Problem)据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人到,于是决定了一个自杀...
这是我自己写的一个josephus算法,使用顺序表做的
Josephus程序.vi. labview例程
Josephus 问题的 C 语言代码 ,链表实现,有查找抄作
定义一个链表类和Josephus类,解决Josephus问题。Hint:链表类的对象是Josephus类的成员
约瑟夫(Josephus)环问题:编号为1,2,3,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止。报m的人...
自己用VC编写的解决Josephus问题,能够根据任何输入得出最终结果,还算健壮,供大家参考,如有好意见欢迎讨论