#2034. 新约瑟夫游戏
新约瑟夫游戏
Description
你一定听说过经典的“约瑟夫”问题吧?现在来组织一个皆大欢喜的新游戏(图9.4-5):
假设n个人站成一圈,从第1人开始交替的去掉游戏者,但只是暂时去掉(例如,首先去掉2),直到最后剩下唯一的幸存者为止。幸存者选出后,所有比幸存者号码高的人每人将得到1块钱,并且永久性地离开,其余剩下的人将重复以上过程,比幸存者号码高的人每人将得到1块钱后离开。一旦经过这样的过程后,人数不再减少,最后剩下的那些人将得到2块钱。请计算一下组织者一共要付出多少钱?
如图9.4-5所示,第一轮有5人,幸存者是3,所以4、5得到1块钱后离开,下一轮幸存者仍然是3,因此没有人离开,所以每人得到2块钱,总共要付出2+2*3=8块钱。
Format
Input
一行一个整数n,不超过32767。
Output
一行一个整数,不超过65535,表示总共要付出多少钱。
Samples
10
13
Limitation
1s, 64MB for each test case.
Statistics
Related
In following homework: