Description

Input

Output

Sample Input

Sample Output

题解

复制个鏼爷的题解。。。

砝码两两互为倍数关系，从小到大排个序，可以发现不同的砝码种类数是log(10^9)级别的，只有30左右。
根据贪心的思想，砝码从小到大依次装入一定是最优的
把每个容器的容量写成砝码大小的进制表示，比如当有3,9,18,54这些种类的砝码时，133的容量可以写成2*54+1*18+0*9+2*3+1，末尾的+1永远用不上，可以舍弃，那么各位从低到高分别是(2,0,1,2)。
把所有容器都写成这种表示，并把同一位上全部累加。比如说我们还有一个容器(0,1,2,0)，那么两个容器累加的结果就是(2,1,3,2)。
当我们正在放大小为3的砝码时，就使用最低位上的容量。比如我们只有1个大小为3的砝码，那么塞入以后剩余容量为(1,1,3,2)。接下来要放大小为9的砝码，最低位上的那个1就永远用不上了。假如我们有2个9，而第二位上只有1的容量，那么就往高位借一个18拆成两个9，变成(2,3,2,2)，然后塞入后剩余(2,1,2,2)。以此类推。
当剩余容量不够再放入时即停止，当前已放入的砝码个数即为最优答案。