[长郡中学2004]慈善的约瑟夫

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 jose.in 输出文件 jose.out

慈善的约瑟夫

【问题描述】

你一定听说过约瑟夫问题吧？即从n个人中找出唯一的幸存者。现在老约瑟夫将组织一个皆在欢喜的新游戏，假设n个人站成一圈，从第1个人开始交替的去掉游戏者，但只是暂时去掉（例如首先去掉2），直到最后剩下唯一的幸存者为止。幸存者选出后，所有比幸存者号码高的人每人将得到1TK（一种货币），永久性离开。其余剩下的人将重复以上的过程，比幸存者号码高的人每人将得到1TK后离开。经过这样的过程后，一旦人数不再减少，则最后剩下的那些人将得到2TK。请你计算一下老约瑟夫一共要付出多少钱？

如图，第一轮有5人，幸存者是3，所以4、5得到1TK后离开，下一轮幸存者仍然是3，因此没有人离开，所以每人得到2TK，游戏结束，总共要付出2+2*3=8TK。

【输入】

只有一个整数：n；1≤n≤32767，表示参加游戏的人数。

【输出】

只有一个整数，不超过65535，表示总共要付出的钱数。

【样例】

jose.in jose.out

10         13