UVA 11986 - Save from Radiation(推理)

Most of you are aware of Nuclear Power Plant Explosion at Fukushima after devastating earth quake and tsunami. Many people in Bangladesh were seen to be concerned UVA 11986 - Save from Radiation(推理)with radiation. The message says:

BBC Flash news: Japan Government confirms radiation leak at Fukushima nuclear plants. Asian countries should take necessary precautions. If rain comes, remain indoors first 24 hours. Close doors and windows. Swab neck skin with betadine where thyroid area is, radiation hits thyroid first. Take extra precautions. Radiation may hit Philippine at around 4 pm today. If it rains today or in the next few days in *, do not go under the rain. If you get caught out, use an umbrella or raincoat, even if it is only a drizzle. Radioactive particles, which may cause burns, alopecia or even cancer, may be in the rain.

Many people suggested many things. We, the programmer society, were not inactive. We uploaded a picture in a very popular social network website, facenote and said, "There are two ways to be safe from radiation. One is the Disky way and another is the Buseen way." You may get clear idea of those two ways from the picture.

Anyway, after the explosion of Fukushima Nuclear Power Plant a bottle of water was sent to my laboratory for experiment. But my stupid robot assistant kept it with N identical water bottles of which I can‘t distinguish the special water bottle which came from Japan. I know that if a rat drinks the water from the special bottle, it will die in the 5th minute. Now, I want to identify the special bottle. But I do not like rat either. So, I want to buy minimum number of rats. Can you help me to find out the minimum number of rats I need for identifying the special bottle in 5 minutes?

I forgot to tell you that, only one drop of water from a bottle is enough to find out if the water is safe or not. And you may also give waters from several bottles to a single rat. If one of these bottles is the special bottle then the rat will die, otherwise it will not. And assume that the time to give waters to the rats is negligible, because once you decide the strategy; you may ask the robot assistant to do it. And the robot can do it in no time. And you can also assume that the bottles contain sufficient amount of waters.

Input

Input starts with an integer T (≤ 3000), denoting the number of test cases.

Each test case starts with a line containing an integer N (0 ≤ N ≤ 1016).

Output

For each case, print the case number and the minimum number of rats required for identifying the special bottle.

Sample Input

Output for Sample Input

1
1
2

Case 1: 1

Case 2: 2

Notes

1.      For case 2, the robot assistant kept the special bottle with 2 identical bottles. So, there are 3 bottles, one of them is the special bottle. The minimum number of rats is 2. Because just give a drop from bottle 1 to the 1st rat and a drop from bottle 2 to the 2ndrat. If the 1st rat dies, so it‘s clear that bottle 1 is the special one. If the 2nd rat dies, then the second bottle is the special one. And if none of them dies, then the 3rd bottle is the special bottle. So, 2 rats are enough. But there are other options, too. Like give the first rat two drops from bottle 1 and 2. And give the second rat a drop from bottle 2. Then the special bottle can also be determined. So, there can be many options, but you need at least 2 rats.

题意:给定n,现在有n瓶正常的瓶子,外加一瓶带辐射的瓶子,小白鼠在喝了带辐射瓶子的水,5分钟会死,问如何用最少的小白鼠在5分钟内找出带辐射的瓶子。
思路:推理。每只小白鼠有活和死两个状态,这样m只小白鼠就可以表示2^m种状态了,对应就是2^m个瓶子。这样就能求最少需要的老鼠数了,但是要注意,n很大,如果用直接开log2去写会有精度误差。
代码:
#include <stdio.h>
#include <string.h>
#include <math.h>

int t;
long long n, one = 1;

int main() {
	int cas = 0;
	scanf("%d", &t);
	while (t--) {
		scanf("%lld", &n);
		int m = 0; n++;
		while ((one<<m) < n) {m++;}
		printf("Case %d: %d\n", ++cas, m);
	}
	return 0;
}


UVA 11986 - Save from Radiation(推理)

上一篇:高内聚,低耦合


下一篇:队列简单实现