三进制 处女座的砝码 高精度

题目链接:https://ac.nowcoder.com/acm/contest/327/C

给你一个数n(非常大,10^1000),问最少要多少个砝码可以将其表示

分析:每个砝码有三种选择,放物体对面,放物体同侧,以及不放,那就可以用三进制表示,不放0,对面1,同侧2.

比如说26,它的三进制是222,则所有222以内的数都可以用1,3,9这三个砝码来表示,但是我们会看到222的实际意义是都放在同侧,那很明显是表示不了的,事实上222可以转化为100-1,意思就是27放在对面,而砝码1放在同侧,这样称出来就是26了,具体怎么话的可以看知乎大佬的回答https://www.zhihu.com/question/30164499

也就是我们的三进制事实上使用1,-1,0三个来表示,比如1,3,9,27相加为40,那么40以内的数都可以用这四个砝码来表示。

最后等比数列求和可以循环一个个来,比pow快一些,就是sum*k+1(k是公比)

PS:样例真坑人,故意弄几个不是3的倍数来误导人

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=1<<30;
const int maxn=1e5+7;
const double pi=acos(-1);
const int mod=1e9+7;
int main(){
    long double n,ans=1,sum=1;cin>>n;
    while(sum<n){
        sum=sum*3+1;
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}

 

上一篇:今天到底第几天222林林


下一篇:JavaScript