Preparing NOJ

约瑟夫问题

1000ms 65536K

Description:

你一定听说过约瑟夫问题。它的结果是找出了 N 个人中唯一的幸存者。现在你要参与一个新的游戏,它的结果比原先那个游戏更令人满意。假设 N 个游戏者站成一个圈。从编号为 1 的游戏者开始每隔一个人暂时性地去掉一个人(比如一开始去掉的是 2 号)直到最后还剩一个人。当幸存者产生后所有比他编号高的游戏者将从约瑟夫那里获得 1 孟加拉币,他们也将永久地离开游戏。对于剩下的游戏者也将进行同样的操作。当某一次操作以后没有人退出游戏,那么游戏中还剩下的人将获得 2 孟加拉币并且游戏结束。你的任务就是查明约瑟夫最终一共要付给游戏者多少钱?

比如,共有 5 人参加游戏,第一轮的幸存者是 3 号,所以 4 号和 5 号游戏者将获得 1 孟加拉币并离开游戏。再下一轮中幸存者仍然是 3 号,因此没有人应该离开,所以剩下的每个人将获得 2 孟加拉币并且游戏结束。所以约瑟夫一共要付( 2 + 2 x 3 =) 8 孟加拉币。

Input:

每一个测试数据的输入占一行,是一个不超过 32,767 的整数。文件结束的同时输入结束。

Output:

每一个测试数据的输出占一行,是一个不超过 65,535 的整数,代表约瑟夫共要付出的钱数。

Sample Input:

5
10
7

Sample Output:

8
13
14

Note:

undefined

本题由旧版NOJ导入,来源:NUPT ACM

Info

NOJ

Provider NOJ

Code NOJ1571

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet