2386: Find the Coin 一个天平,一堆石子中只有一个比较重，用最少的次数找出

kongming_acm

于 2010-11-11 15:56:00 发布

阅读量814

点赞数

分类专栏： joj acm_数学问题文章标签： integer output input n2

本文链接：https://blog.csdn.net/kongming_acm/article/details/6002920

版权

joj acm_数学问题专栏收录该内容

63 篇文章

订阅专栏

这是一个关于找寻一堆硬币中唯一较重硬币的问题，通过最少的天平称重次数来确定哪一枚是重的。给定硬币数量N，需要求解找到这枚硬币的最小称重次数。案例中，Keenas解决了仅用两次称重就能找到的问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

2386: Find the Coin

Result	TIME Limit	MEMORY Limit	Run Times	AC Times	JUDGE
	3s	8192K	213	104	Standard

One day, Φ has 8 golden coins. He knew one of them is heavier than others. He wants to find out it. Then he wants to borrow X’s scale. But X is so mean. He said Φ must pay $10 for every use. So Φ ask Keenas for help. After a while , Keenas work out that it just need two times to weight it.

After that, Φ and Keenas want to knew if they have N golden coins, how many times they should use the scale at least? Please help them.

Input

There are many cases.In every case,there is a integer N (0<=N<20000)

Output

Output the minmum number to use scale to find the coin.One case in a line.

Sample Input

Sample Output

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[21000];
int main()
{
    f[2]=f[3]=1;
    for(int i=4;i<=20000;i++)
    {
        if(i%3==0) f[i]=f[i/3]+1;
        else if(i%3==1) f[i]=max(f[i/3]+1,f[i/3+1]+1);
        else f[i]=max(f[i/3+1]+1,f[i/3]+1);
    }
    int n;
    while(scanf("%d",&n)==1)
    {
        printf("%d/n",f[n]);
    }
    return 0;
}