3934新约瑟夫游戏(josephus)

3934   新约瑟夫游戏(josephus)

题目描述

你一定听说过经典的约瑟夫问题把?现在来组织一个皆大欢喜的新游戏(图9.4-5):假设n个人站成一圈,从第1个人开始交替的去掉游戏者,但只是暂时去掉(例如,首先去掉2),直到最后剩下唯一的幸存者为止。幸存者选出后,所有比幸存者号码高的人每人将得到1块钱,并且永久性地离开,其余剩下的人重复以上过程,比幸存者号码搞的人每人将得到1块钱离开。一旦经过这样的过程后,人数不再减少,最后剩下的那些人将得到2元。请计算一下组织者一共要付出多少钱?
如图9.4-5所示,第一轮有5人,幸存者是3,所以4、5得到1块钱后离开,下一轮幸存者仍然是3,因此没有人离开,所以每人得到2元,总共要付出2+2*3=8元

输入格式:

一行一个整数n,不超过32767

输出格式:

一行一个整数,不超过65535,表示总共要付出多少钱
输入样例 复制
10
输出样例 复制
13

说明

3
3
通过提交
时空限制1000ms/64mb
题目来源
评测方式在线评测
题目类型递推
难        度