2191: 最少的次数

Time Limit: 1 Sec  Memory Limit: 512 MB

Submit: 553  Solved: 73

[][][]

Description

这一天，成都东软学院ACM团队举办了一场游戏。游戏是这样的：

在桌上有一堆糖，其中有一颗糖与其他糖外观一模一样，但重量却明显轻。现在得知桌上共有N颗糖，还有一个天平，问最少需要多少次一定能准确的找出该糖？今天作为比赛中的你，相信这一问题应该不是什么难事，加油吧！

Input

第一行包含一个数m，表示后面有m个测试数据

第二行起共m行有一个数n，(1 <= n <= 263-1)表示糖的个数

Output

输出格式如下：

首先输出Case n: (n表示答案计数，其中Case后面包含一个空格，'：'后面包含一个空格，请注意！）

后面输出相应的最小次数

Sample Input

2

1

2

Sample Output

Case 1: 0

Case 2: 1

HINT

 

Source

 

#include 
      
       int main(){    int n;    scanf("%d",&n);    int t=0;    long long m;    while(n--)    {        int k=0;        scanf("%lld",&m);        while(m>1)        {            if(m%3!=0)            m=m+(3-m%3);            m/=3;            k++;        }        printf("Case %d: %d\n",++t,k);    }    return 0;}
      

相比2分，三分能算出更少的次数，如果是分成4份以上就成堆无法判断了！

把糖果平均分成3份，不能整除的补成能被3整除的，看它能被3除几次！能除一次，就是3份比较1次，排除掉另外三分之二的糖果！ 

也就是算log以3为底的m