10004_约瑟夫问题

2022-5-16 18:16| 发布者: Hocassian| 查看: 120| 评论: 0|原作者: 肇庆学院ACM合集

摘要:
C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504330192500-Problem List-采集的数据-后羿采集器.html

Pro.ID

10004

Title

约瑟夫问题

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=10004

AC

240

Submit

571

Ratio

42.03%

时间&空间限制

  • Time Limit: 100000/50000 MS (Java/Others)     Memory Limit: 32768/32768 K (Java/Others)
  • 描述

    n个土匪行走江湖多年,专门劫富济贫,每次行动之后会给自己留一点财宝养家糊口(不行啊?!土匪也是人。土匪也有家呀)。终于有一天,他们老了,累了,于是在一个山洞里集合,决定如何分配多年来积聚的财宝。

    大土匪说:所有财宝我占一半,剩下你们分吧。

    众人说:凭什么!

    小土匪说:所有财宝我占一半,剩下你们分吧。

    众人说:白日做梦!

    不大不小中土匪说:....

    众人说:痴心妄想!!

    不大不小中土匪:我还没说呢....是这样的,我看咱们的东西也不多,只有300亿英镑,也不够造一艘宇宙航母。全部人平分的话,退休生活会很艰苦。不如全部留给一个幸运的人吧。好不好。

    众人心里想:那个幸运的人一定是我。于是说:那个幸运的人一定不是你!

    不大不小中土匪:我想出一个办法,大家围成一个圈,每个人一个编号,从1到n。即大土匪(编号1)的下一个是二土匪(编号2),二土匪的下一个是三土匪(编号3)....第n个土匪(编号n)的下一个是大土匪。然后大家选定一个正整数X。大土匪开始数1,下一个人数2....数到X的那个人,淘汰离开圈子,下一个人重新从1开始数,数到第X的那个人也被淘汰。如此循环,直到最终只剩一个人。这个人就是幸运儿。大家认为这个方案怎么样?

    众土匪虽然都是本科以上的高材生,但由于平时干的都是体力活,很少动脑筋,这次也懒得动脑筋再想另一个方案了。于是方案获得通过,且附加了一个条件,凡是被淘汰者,要被枪决,以防将来向幸运儿敲竹杠打秋风拉赞助。。。。当然,枪决之前,少不了要豪饮几斤黄酒狂吞几只炸鸡翅挥泪话别英勇就义等等场景。

    接下来就是紧张刺激惊心动魄扣人心弦的残暴血腥惨无人道充满江湖味道的场面(由于场面太暴力,此处被删去五万零三百二十七字)。

    天亮了,不大不小中土匪拖着疲惫的身躯,眯着通红的双眼,右手拽着支票,左手拿着手枪,嘴上叼着烟斗,缓步走出山洞。风吹过,把他的头发吹乱了。风中隐约听到他喃喃自语:一帮没看过约瑟夫问题的傻波依...

    输入

    有多个测试用例,每个测试用例占单独一行。每个测试用例有2个正整数n和x ( 0 < n < 10000000,0 < x < 10000000),分别表示土匪人数以及选定的那个数字x。n和x之间有一个空格作为分隔。

    最后一个测试用例n=0 x=0,表示输入结束。

    输出

    Description

    n个土匪行走江湖多年,专门劫富济贫,每次行动之后会给自己留一点财宝养家糊口(不行啊?!土匪也是人。土匪也有家呀)。终于有一天,他们老了,累了,于是在一个山洞里集合,决定如何分配多年来积聚的财宝。

    大土匪说:所有财宝我占一半,剩下你们分吧。

    众人说:凭什么!

    小土匪说:所有财宝我占一半,剩下你们分吧。

    众人说:白日做梦!

    不大不小中土匪说:....

    众人说:痴心妄想!!

    不大不小中土匪:我还没说呢....是这样的,我看咱们的东西也不多,只有300亿英镑,也不够造一艘宇宙航母。全部人平分的话,退休生活会很艰苦。不如全部留给一个幸运的人吧。好不好。

    众人心里想:那个幸运的人一定是我。于是说:那个幸运的人一定不是你!

    不大不小中土匪:我想出一个办法,大家围成一个圈,每个人一个编号,从1到n。即大土匪(编号1)的下一个是二土匪(编号2),二土匪的下一个是三土匪(编号3)....第n个土匪(编号n)的下一个是大土匪。然后大家选定一个正整数X。大土匪开始数1,下一个人数2....数到X的那个人,淘汰离开圈子,下一个人重新从1开始数,数到第X的那个人也被淘汰。如此循环,直到最终只剩一个人。这个人就是幸运儿。大家认为这个方案怎么样?

    众土匪虽然都是本科以上的高材生,但由于平时干的都是体力活,很少动脑筋,这次也懒得动脑筋再想另一个方案了。于是方案获得通过,且附加了一个条件,凡是被淘汰者,要被枪决,以防将来向幸运儿敲竹杠打秋风拉赞助。。。。当然,枪决之前,少不了要豪饮几斤黄酒狂吞几只炸鸡翅挥泪话别英勇就义等等场景。

    接下来就是紧张刺激惊心动魄扣人心弦的残暴血腥惨无人道充满江湖味道的场面(由于场面太暴力,此处被删去五万零三百二十七字)。

    天亮了,不大不小中土匪拖着疲惫的身躯,眯着通红的双眼,右手拽着支票,左手拿着手枪,嘴上叼着烟斗,缓步走出山洞。风吹过,把他的头发吹乱了。风中隐约听到他喃喃自语:一帮没看过约瑟夫问题的傻波依...

    Input

    有多个测试用例,每个测试用例占单独一行。每个测试用例有2个正整数n和x ( 0 < n < 10000000,0 < x < 10000000),分别表示土匪人数以及选定的那个数字x。n和x之间有一个空格作为分隔。

    最后一个测试用例n=0 x=0,表示输入结束。

    Output

    对应每个测试用例,单独输出一行:幸运儿的编号。

    Sample Input

    10 7
    5 8
    0 0

    Sample Output

    9
    1

    Author

    样例输入

    10 7
    5 8
    0 0

    样例输出

    9
    1

    提示

    作者


    路过

    雷人

    握手

    鲜花

    鸡蛋

    最新评论

    返回顶部