Question

acm有假币问题，你们怎么做的额？？我总是wrong answer！！

居然有假币！！！
事情是这样的，现在猪肉涨了，但是农民的工资却不见涨啊，没钱怎么买猪肉啊。渊子这就去买猪肉，结果找来的零钱中有假币！！！可惜渊子一不小心把它混进了一堆真币里面去了。现在知道假币的重量比真币的质量要轻。给你一个天平，请用最快的时间把那个可恶的假币找出来
1≤n≤2^30,输入0结束程序
最少要称几次一定能把那个假币找出来。

我的代码是：

#include<stdio.h>
int main(){
int mi(int n);
int i,t;
scanf("%d",&t);
while(t>=1&&t<=mi(30)){
if(t==1)
printf("%d\n",t);
else
for(i=1;i<=30;i++)
if(t<mi(i))
{printf("%d\n",i-1);
break;}
scanf("%d",&t);
}
return 0;
}
int mi(int n){
int i,s=1;
for(i=1;i<=n;i++)
s=2*s;
return s;
}
怎么错了呢？？

Answer 1

二分查找。比如8个，第一次拆成4 4，第二次 22 第三次 找出。
也就是(int)log2N

追问

#include
#include
int main(){
int t,k;
double j,i,s;
scanf("%d",&t);
while(t!=0){
j=log(t);
i=log(2);
k=(int)(j/i);
printf("%d\n",k);
scanf("%d",&t);
}
return 0;
}
改成这样了，依然wrong answer，这究竟哪错了呢？

追答

你把链接贴出来吧 我说错了 因为他是只可能小，三分就比二分快。比如9个 分成三分 只需要两次。

追问

这个是链接：http://icpc.ahu.edu.cn/OJ/Problem.aspx?id=158
这个是改过的程序：
#include
int main(){
int n,i,s=1,j=1;
scanf("%d",&n);
while(n!=0){
if(n==1)
printf("%d\n",0);
else
for(i=0;i<32;i++){
s=3*s;
if(s<n)
j++;
else
{printf("%d\n",j);break;}
}
s=1;j=1;
scanf("%d",&n);
}
return 0;
}

追答

非常抱歉最近有点忙要加班。刚才帮你看了下。

思想就是，三分。如果遇到不能三分的比如11会分成3 4 4等，补足到12再分。

这题的细节还是不少的，

递归算法如下(不好意思实在忙懒得改易读性了)

# include <stdio.h>   

int count(int n){

return n == 1 ? 0  : 1+count( n%3 ? (n+3-n%3)/3 :n/3);

}

int main() {

int n;

while(scanf("%d",&n)==1 && n != 0)printf("%d\n",count(n));

}

下面附件这个非递归好理解，特意用文件形式，你可以先自己写，写不出再看。

Answer 2

是对3取对数的，
(int)log3(N)+1
有一篇论文里有提到。

因为每一次的对果有三种大小等，所以对3取对数。

追问

应该不是（int）log3(N)+1；因为如果N=9时，按这种算式得出3，而其实是2，将9分为3,3,3即可两次称的；后来改成这样还是错了！！
#include
int main(){
int n,i,s=1,j=1;
scanf("%d",&n);
while(n!=0){
if(n==1)
printf("%d\n",0);
else
for(i=0;i<32;i++){
s=3*s;
if(s<n)
j++;
else
{printf("%d\n",j);break;}
}
s=1;j=1;
scanf("%d",&n);
}
return 0;
}

追答

刚才提交了一下，AC了。
我的想法是，每次分成三堆，尽量的均匀，然后称完之后最坏的情况就是那一堆最大的继续称。

#include
#include
#include
#include
#include
#include
using namespace std;

int main()
{
int n,m;
int i,j,k;
int ans=0;
//while(scanf("%s%d",s,&m)!=EOF)
while(scanf("%d",&n)!=EOF&&n>0)
{
if(n==1)
{
puts("0");
continue;
}
ans=0;
while(n>3)
{
if(n%3==0)n/=3;
else n=n/3+1;

ans++;
}
printf("%d\n",ans+1);
}
return 0;
}

/*

*/