2765:疯狂生长

时间限制:2 S   /  内存限制:65536 KB
AC:88   /  Submit:322
问题描述

农夫约翰希望自己的植物生长的越快越好,于是他发明了一种疯狂药剂,凡是被这种药剂作用过的植物都会比一般植物生长的要快,但麻烦的是,约翰把疯狂药剂与其他药剂放在了一起,一时间难以分辨!

约翰想了一种方法:他可以从任意数量的药剂中分别提取一些药液混合形成一种新的药剂,然后把这种药剂作用给一株植物,如果该植物生长的很快,则说明疯狂药剂参与了混合。

现在约翰想知道,在最坏的情况下,他至少需要多少株植物才能确定哪瓶药剂是疯狂药剂。

输入描述

只有一组案例,输入一个正整数 n 代表药剂的总数。(1 <= n <= 2e9)

输出描述

一个数字,代表在最坏的情况下,他至少需要多少株植物才能确定哪瓶药剂是疯狂药剂,然后换行。

样例输入复制样例

3

样例输出

2

提示说明

我们可以先把药剂编号,分别为药剂1,药剂2,药剂3。

我们先给第一株植物使用药剂1和药剂2的混合液,如果该植物没有疯狂生长,则说明药剂3是疯狂药剂。

如果该植物疯狂生长了,则说明药剂1和药剂2中有一瓶是疯狂药剂,此时我们只需要拿这两种药剂中的其中一瓶单独做一次实验即可见分晓。

由于题目要求是在最坏情况下需要多少株植物,所以答案是2。

相关

19-20(2)第1次线上赛


Copyright 2016 - 2024 XUJC ACM Team
闽ICP备2020022076号-1