问题1372--约瑟夫环问题

1372: 约瑟夫环问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 365  解决: 157
[状态] [讨论版] [提交] [命题人:]
题目描述

Klinger某野战外科医院的一员,他负责处理一些杂事。美军准备抽奖选择一些幸运的人(X个人)回国进行招兵宣传。Klinger需要你的帮助。

    这次抽奖是将本单位的所有成员排成一排,然后从一叠卡片的顶部取卡片,卡片号为N;从队列中从1N报数,每次报到N时,第N个人离开队列,然后下一个人再从1开始报数。当报数报到队列结束的时候,再从一叠卡片的顶部取下一张卡片,再从剩余的队列中从第一人开始根据新的卡片号进行报数。队列中最后的X个人可以回家。

Klinger在选拔过程开始前叠好了一叠卡片。然而,到了最后一分钟他才知道有多少人参加。请你编写程序,基于Klinger的卡片和队列中人员的数量,告诉他队列中哪些位置的人可以回家。可以确定最多用20张卡片。

例如,队列中有10人,2个幸运位置,卡片号码为35432,队列中位置18的人可以回家。过程如下:

队列1 2 3 4 5 6 7 8 9 10N=10X=2,卡片次序为35432

3:划掉369;剩12457810

5:划掉7;剩1245810

4:划掉5;剩124810

3:划掉4;剩12810

2:划掉210;剩18

输入

每个测试用例在一行中给出22个整数。第一个整数(1<=N<=50)给出参加抽奖的人的数量,第二个整数(1<=X<=N)给出有多少个幸运的回家位置。后面的20个整数给出前20张卡片上的号码。卡片号码是从111的整数。

输出

对于每个输入行,在一行中输出“Selection #A”,其中A是输入的测试用例编号,从1开始编号,下一行给出Klinger要获得的幸运位置的列表,幸运位置的列表后是一个空行。

样例输入 Copy
10 2 3 5 4 3 2 9 6 10 10 6 2 6 7 3 4 7 4 5 3 2
47 6 11 2 7 3 4 8 5 10 7 8 3 7 4 2 3 9 10 2 5 3
样例输出 Copy
Selection #1
1 8 

Selection #2
1 3 16 23 31 47 

来源/分类