最少砝码
前n个可以表示0~k;
第n+1个为x（x>k）;
最大可测maxn=k+x;
第n+1个和前n个放两边 可测得x-k；
让x-k=k+1，得到x=2k+1；
maxn=3k+1；
k+1 可以用(2k+1) - (k-0) 表示
k+2 可以用(2k+1) - (k-1) 表示
…
2k+1 可以用(2k+1) - (0) 表示
2k+2 可以用(2k+1) + (1) 表示
…
3k+1 可以用(2k+1) + (k) 表示
这样n+1个砝码可以表示出0～3k+1
然后可以根据这个max[i+1] = 3*max[i]+1
然后运用数学知识转化为一个公式即可
a[i]表示用i个砝码 能够构成的 最大可测量重量(此时的范围自然也对应着0~a[i])
a
[
0
]
=
0
a[0]=0
a[0]=0
a
[
1
]
=
2
∗
0
+
1
=
1
,
该次新增砝码重量为
2
∗
0
+
1
=
1
a[1]=2*0+1=1,该次新增砝码重量为 2*0+1=1
a[1]=2∗0+1=1,该次新增砝码重量为2∗0+1=1
a
[
2
]
=
3
∗
1
+
1
=
4
,
该次新增砝码重量为
2
∗
1
+
1
=
3
a[2]=3*1+1=4 ,该次新增砝码重量为 2*1+1=3
a[2]=3∗1+1=4,该次新增砝码重量为2∗1+1=3
a
[
3
]
=
3
∗
4
+
1
=
13
,
该次新增砝码重量为
2
∗
4
+
1
=
9
a[3]=3*4+1=13 ,该次新增砝码重量为 2*4+1=9
a[3]=3∗4+1=13,该次新增砝码重量为2∗4+1=9
甚至可以把规律整理为公式(等比数列的和
a
1
(
1
−
q
n
)
/
(
1
−
q
)
a1(1-q^n)/(1-q)
a1(1−qn)/(1−q)，q=3 , a1=1）
a
[
i
]
=
(
3
i
−
1
)
/
2
>
=
K
=
=
>
i
=
l
o
g
3
(
2
∗
K
+
1
)
a[i]=(3^i-1)/2>=K ==> i=log_3(2*K+1)
a[i]=(3i−1)/2>=K==>i=log3(2∗K+1)
res=log(2*K+1)/log(3)
#include<bits/stdc++.h>
using namespace std;
#define int long long
int K;
signed main(){
cin>>K;
int res=0;
int sum=0;
while(true){
res++;//加一个砝码
sum=sum*3+1;//能称出的 最多数量
if(sum>=K){
cout<<res;
break;
}
}
return 0;
}
