乔普是个很聪明的孩子,听说有一批葡萄酒被混入一瓶毒酒,由于价格便宜,打算将这一批酒购来,找出那瓶毒酒,再以高价出售,由于每瓶葡萄酒的包装和味道完全相同,一时无法鉴定出哪瓶是毒酒,也不可能一一去试尝,他想到他的朋友伊娃,她养了一大群小白鼠,想用小白鼠去做实验,由于酒太多了,所以没有那么多去尝试每一瓶酒。这种毒酒的毒性比较弱,小白鼠一旦品尝后,毒性会在24小时后发作。所以乔普想请你帮他设计一个方案的,这么多瓶酒,至少需要多少只小白鼠,一次性,喝其中的某些酒,要在第二天后找出哪一瓶毒酒。
【数据范围约定】
30% 的测试点输入数据保证 1≤n≤1000;
60% 的测试点输入数据保证 1≤n≤1000000;
80% 的测试点输入数据保证 1≤n≤2147483647;
100% 的测试点输入数据保证 1≤n≤264;
样例1说明:2瓶酒,1只小白鼠,喝其中的一瓶,第二天挂了,说明这瓶有毒,否则相反,另一瓶有毒。
样例2
以下是其中的一个方案:
有6瓶酒,至少三只小白鼠
第一只小白喝其中的2 3 6号瓶酒
第二只小白喝其中的5 6号瓶酒
第三只小白喝其中的1 3 5号瓶酒
第二天
如果只有第三只挂了,说明是第1号瓶是毒酒;
如果只有第一只挂了,说明是第2号瓶是毒酒;
如果有一只和第三只挂了,说明是第3号瓶是毒酒;
如果一只都没有挂,说明是第4号瓶是毒酒;
如果第二和第三只挂了,说明是第5号瓶是毒酒;
如果是第一和第二只挂了,说明是第6号瓶是毒酒;
注意:方案很多种,找出一种即可