处女座的砝码
链接:
题目描述
处女座热爱做物理实验,为了实验,处女座必须要精确的知道物品的质量。处女座准备自己设计一套砝码,每一个砝码都是正整数,这套砝码必须能够精确测量出n以内所有正整数的质量,处女座想要知道至少需要多少个砝码。你可以在天平的任意一边放置砝码。
输入描述:
一行,一个正整数n 1<=n<=10^1000
输出描述:
一个整数,表示最少的砝码数。
示例1
输入
20
输出
4
说明
你可以选择1,2,6,11 1=1 2=2 3=1+2 4=6-2 5=6-1 6=6 7=6+1 8=6+2 9=6+2+1 10=11-1 11=11 12=11+1 13=11+2 14=11+2+1 15=11+6-2 16=11+6-1 17=11+6 18=11+6+1 19=11+6+2 20=11+6+2+1 题意:每个砝码可以放左边,不放和右边,很容易联想到三进制,所以按照3 进制排列即可,选择砝码如下:1,3,9,27,…
1 import java.math.BigInteger; 2 import java.util.Scanner; 3 4 public class Main { 5 public static void main(String[] args) { 6 Scanner cin = new Scanner(System.in); 7 BigInteger n = cin.nextBigInteger(); 8 BigInteger now = BigInteger.valueOf(1); 9 int cnt = 1;10 while(n.compareTo(now)>0) {11 cnt ++;12 now = now.multiply(BigInteger.valueOf(3));13 now = now.add(BigInteger.valueOf(1));14 }15 System.out.println(cnt);16 }17 }