Codeforces 959 E Mahmoud and Ehab and the xor-MST

Discription

Ehab is interested in the bitwise-xor operation and the special graphs. Mahmoud gave him a problem that combines both. He has a complete graph consisting of n vertices numbered from 0 to n - 1. For all 0 ≤ u < v < n, vertex u and vertex v are connected with an undirected edge that has weight (where is the bitwise-xor operation). Can you find the weight of the minimum spanning tree of that graph?

You can read about complete graphs in https://en.wikipedia.org/wiki/Complete_graph

You can read about the minimum spanning tree inhttps://en.wikipedia.org/wiki/Minimum_spanning_tree

The weight of the minimum spanning tree is the sum of the weights on the edges included in it.

Input

The only line contains an integer n (2 ≤ n ≤ 10¹²), the number of vertices in the graph.

Output

The only line contains an integer x, the weight of the graph's minimum spanning tree.

Example

Input

Output

Note

In the first sample: The weight of the minimum spanning tree is 1+2+1=4.

依次考虑加入边权 1,2.....的边，看能否使图的连通性产生变化。

发现只有 2^i 的边能对图的连通性产生变化，并且有用的边的数量也很好计算 (不妨画一个图就能很快的发现这个规律)，所以就可以直接递归/迭代做了。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

inline ll LB(ll x){ return x&-x;}

ll solve(ll x){

	return x==1?0:(solve(x>>1)*2ll+(x>>1)+((x&1)?LB(x-1):0));

}

int main(){

	ll n; scanf("%I64d",&n);

	printf("%I64d\n",solve(n));

	return 0;

}

巴特西

Codeforces 959 E Mahmoud and Ehab and the xor-MST

最新文章

热门文章