问题1009--josephus问题

1009: josephus问题

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 64 MB

题目描述

josephus问题其实就是一个游戏,一群小孩围成一个圈,设置一个数,这个数是个小于小孩总数大于0的一个整数,从第一个小孩开始报数,当其中一个小孩报到你设置的那个数的时候离开那个圈,这样一来反复报下去,直到只剩下最后一个小孩的时候那个小孩就是胜利者。 现在的问题是设n个人围坐在一个圆桌周围,现在从第s个人开始报数,数到第m个人,让他出局;然后从出局的下一个人重新开始报数,数到第m个人,再让他出局,……,如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是:对于任意给定的n, s和m,求出这n个人的出局序列。请以n = 9, s = 1, m = 5为例,人工模拟Josephus的求解过程以求得问题的解。 出局人的顺序为5, 1, 7, 4, 3, 6, 9, 2, 8。 本题可以对多个测试案例进行测试。

输入

第一行输入测试案例数T 以下T行,每一行是一个测试案例,分别输入n,s,m,以一个或多个空格隔开

输出

每个测试案例输出2行, 第一行输出出局顺序 第2行输出"** win.",其中**是胜利者编号,即最后出局者

样例输入 Copy

1
9 1 5

样例输出 Copy

5 1 7 4 3 6 9 2 8
8 win.

来源/分类

yhr