boj 237

Description

Greetings, Libras.

一个不透明的袋子里装有若干个重量是1的小球, 袋子的重量忽略不计. 只知道小球的数量至少是1, 至多是N.
现在给你一架天平, 你可以自己设计一套砝码, 即砝码的个数与每个砝码的重量都可以自由定义(每个砝码的重量必须是正整数).
要求不管袋子里有多少个小球, 都可以用这套砝码称出小球的确切数量. 称的次数不限. 每次使用天平只能获得下列三种信息之一: 左边比右边重; 两边等重; 右边比左边重.

 

给你已知的N, 请问设计方案至少需要多少个砝码?

 

Input

多组CASE(不超过50000组).
每组CASE一行, 一个正整数N. 1<=N<=10^9.
输入以EOF结束.

Output

每组一行, 一个正整数, 最少需要的砝码个数.

Sample Input

4
10
2134516

Sample Output
2
3
14

Hint

对于sample 1: 可以设计使用2个砝码, 重量分别为1, 3. 则重量1~4都可以称出.

 

Source

wolf5x 

思路：

首先对于N，1和N是无需称量的，比2小的肯定是1，比N-1大的肯定是N。

此题的规律为，当前所有砝码的和为sum，则能称量1~sum个，而对于sum+1重量的无需直接称量

，可以通过称量sum+2的，这样通过sum和sum+2即可确定sum+1,而称量sum+2，则可以通过增

加一个2*sum+2的砝码，通过（2*sum+2）-sum得到，所以可以如下推导：

sum= 0,cur = 2;

sum = 2,cur = 2*sum+2=6

sum = 8,cur = 2*sum+2=10

...

.....

如此下去，直到sum>=N-1。

代码：

#include<iostream>
using namespace std;

int main()
{
	int n;
	while(~scanf("%lld",&n))
	{
		int sum = 0,cnt = 0,cur = 2;
		while(n-1>sum)
		{
			sum+=cur;
			cur = 2*sum+2;
			cnt++;
		}
		printf("%d\n",cnt);
	}
}