Description

时间限制: 1 Sec  内存限制: 128 MB
提交: 66  解决: 45
[提交] [状态] [讨论版] [命题人:fengyecong] [Edit] [TestData]
题目描述
背景：
tybAU后开始胡思乱想。
题目描述：
一天，tyb带领着他的骑士团开始征服世界了！
Tyb所在的世界比较奇怪，城市与城市间的有向道路形成一个以1为根，有n个点的完全二叉树。即城市i有通向2*i与2*i+1城市的路。
Tyb的一次征途是这样的：他可以瞬移到任何一个城市，招兵买马，然后沿着道路将沿途的城市征服。因为tyb战无不胜，以德服人，所以绝不会重复到一个点。
现在tyb想知道，它最少征战多少次才能征服世界。
一句话题意：求一个有n个点的完全二叉树的最小路径覆盖。
输入描述：
一个数n，表示城市数.
输出描述：
一个数ans，即tyb最少征途数。
样例输入：
7
样例输出：
4
数据范围：
对于30%的数据，n<=10^5
对于50%的数据，n<=10^7
对于100%的数据，n<=10^18
来源/分类
fyc