【推导】The 16th UESTC Programming Contest Preliminary L - Foxtrot

时间:2023-12-23 23:52:07

题意:有n瓶药剂,其中只有一瓶药剂有毒。让你用最少的小白鼠试出哪瓶有毒。你只有一次给任意只小白鼠各喂食任意种类药剂的机会。

m只老鼠就能对应2^m种“生死状态”的组合,给每种状态分配一个种类的药剂,然后给每只老鼠喂食“如果它在这种药剂对应的生死状态下死去”的所有药剂,就可以根据发生的死亡情况,分辨出哪瓶药剂有毒。

比如老鼠数有3只。

000 1

001 2

010 3

100 4

110 5

011 6

101 7

111 8

给一号鼠喂4578

给二号鼠3568

给三号鼠2678。

所以答案为(ceil)log2(n)。

#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
int T,n;
int main(){
scanf("%d",&T);
for(;T;--T){
scanf("%d",&n);
if(n==1){
puts("0");
continue;
}
for(int i=1;i<=30;++i){
if((1<<i)>=n){
printf("%d\n",i);
break;
}
}
}
return 0;
}