学步园

// The Archeologist’s Dilemma （考古学家的烦恼）
// PC/UVa IDs: 110503/701, Popularity: A, Success rate: low Level: 1
// Verdict: Accepted
// Submission Date: 2011-05-29
// UVa Run Time: 0.212s
//
// 版权所有（C）2011，邱秋。metaphysis # yeah dot net
//
// 算法：暴力计算 2 的幂会很快达到整数表示的上界，除非用替代方法来计算。以下展示了两种方法，一种
// 是计算 2 的幂直到找到前面相应的位为给定的数字，这种方法可以计算出结果，但是很容易超出 10s 的
// 时间限制以及内存限制。第二种方法是根据以下不等式（假设丢掉的数字共有 K 位，现有的数字为 N，要
// 求的最小幂次为 X）：
//
// N * 10^K < 2^X < (N + 1) * 10^K
// ((logN + K) / log2) < X < ((log(N + 1) + K) / log2)
//
// 第二种方法虽然能获得 AC，但是对于比较大的数，计算时间仍旧很长。由于 2 的幂数字组成是无限的，故
// 不能判定是否没有一个 X 满足给定的条件，所以不能输出 “no power of 2”。
	
#include <iostream>
#include <cmath>
	
using namespace std;
	
void find_smallest_exponent_by_brute_force(long number)
{
	long long unsigned exponent = 7;
	
	string first;
	while (number)
	{
		first.append(1, '0' + number % 10);
		number /= 10;
	}
	
	string result = "821";
	
	while (result.rfind(first) != (string::size_type)(result.length() - first.length())
		|| result.length() < (2 * first.length() + 1))
	{
		int carry = 0;
		for (int i = 0; i < result.length(); i++)
		{
			carry = 2 * (result[i] - '0') + carry;
			result[i] = '0' + carry % 10;
			carry = carry / 10;
		}
		
		if (carry)
		result.append(1, '1');
		exponent++;
	}
	
	cout << exponent << endl;
}
	
void find_smallest_exponent_by_log(long number)
{
	int digits = 0;
	long original = number;
	while (original)
	{
		digits++;
		original /= 10;
	}
	
	for (int k = (digits + 1); ; k++)
	{
		long long down = floor((log10(number) + k) / log10(2));
		long long up = floor((log10(number + 1) + k) / log10(2));
		
		if (up > down)
		{
			cout << up << endl;
			return;
		}
	}
}
	
int main(int ac, char *av[])
{
	long number;
	
	while (cin >> number)
		find_smallest_exponent_by_log(number);
	
	return 0;
}