#28002. 慈善的约瑟夫

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: wl

题目描述

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

例如,第一轮有5人,幸存者是3,所以4、5得到1TK后离开,下一轮幸存者仍然是3,因此没有人离开,所以每人得到2TK,总共要付出(2 + 2 x 3 )= 8TK。

输入格式

输入文件包含一个整数,不超过32767。

输出格式

输出文件包含一个整数,不超过65535,表示总共要付出的钱数。

样例

输入样例
10
输出样例
13

分类标签