![P7649 [BalticOI 2004] Scales (Day1) 题解](http://pic.xiahunao.cn/yaotu/P7649 [BalticOI 2004] Scales (Day1) 题解)
P7649 [BalticOI 2004] Scales (Day1)Link: https://www.luogu.com.cn/problem/P7649题目描述给您一个平衡的臂秤一组砝码和一个物体。这些砝码的重量为1 , 3 , 9 , 27 , 81 , … 1, 3, 9, 27, 81, \dots1,3,9,27,81,…即每个砝码的重量为3 33的幂对于每个整数k ≥ 0 k \ge 0k≥0正好有一块砝码重量3 k 3^k3k。物体的重量是m mm其中m mm是正整数。你的任务是把物体放在左边的秤盘上然后把一些砝码放在左右一个或两个秤盘上使得秤平衡。输入格式第一行包含一个整数m mm。输出格式第一行包含有关放在左秤盘上砝码的信息第一个数字必须为非负整数――放在左秤盘上的砝码个数然后是各砝码重量且按递增顺序数字必须用单个空格分隔。第二行包含与第一行相同格式的有关放置在右秤盘上的砝码的信息。输入输出样例 #1输入 #142输出 #13 3 9 27 1 81输入输出样例 #2输入 #230输出 #20 2 3 27说明/提示数据规模与约定对于100 % 100 \%100%的数据1 ≤ m ≤ 10 100 1 \le m \le 10^{100}1≤m≤10100。题目说明来源于 Baltic Olympiad in Informatics 2004 的 Day 1:SCALES。Solution1. 题意本题的题目背景是使用砝码称量物体质量所有砝码的质量皆为3 33的整数次幂次。现在要求对于一块质量已知放在左盘区的物体如何在左右盘中合理放置这些砝码使得天平平衡。2. 分析首先是托盘天平的读数方法。当物块放在左边放置砝码使得天平平衡那么用右边的砝码总质量减去左边砝码的总质量差值就是物块的质量。由此我们容易想到对于一个砝码如果放在右边就记为正值放在左边记为负值那么本题即可转化为将给定正整数转化为一些3 33的幂次的和减去另一些3 33的幂次的差。上面这个过程的核心原理是平衡三进制。将初始输入的十进制值转化为平衡三进制即可求解。平衡三进制是一种使用− 1 , 0 , 1 -1,0,1−1,0,1三个数码的计数体系。为书写方便一般会使用字母Z \text{Z}Z表示− 1 -1−1的数位。例如对于平衡三进制下的( 1 Z 101 ) balance3 (1\text{Z}101)_\text{balance3}(1Z101)balance3化为十进制的结果是( 1 Z 101 ) balance3 1 × 3 4 ( − 1 ) × 3 3 1 × 3 2 0 × 3 1 1 64 (1\text{Z}101)_\text{balance3}1\times3^4(-1)\times3^31\times3^20\times3^1164(1Z101)balance31×34(−1)×331×320×31164从上面的结果很容易看出64 6464被拆分为了81 , − 27 , 9 , 1 81,-27,9,181,−27,9,1也就是说将27 2727和质量为64 6464的物体放在左侧将81 , 9 , 1 81,9,181,9,1放在右侧即可平衡。参考[1] AT_past202107_g 题解[2] 平衡三进制 on OI-wiki[3] 平衡三进制3. 代码(1) Python# 将十进制转化为平衡三进制defToBalance3(decimal_value:int):currentdecimal_value resultlist()whilecurrent:result.append(current%3)current//3result.append(0)foriinrange(len(result)-1):ifresult[i]2:result[i]-1result[i1]1ifresult[i]3:result[i]0result[i1]1returnresult# 将平衡三进制按照±1划分为左右部分defLeftVsRight(balancebase3sequence:list):leftlist()rightlist()foriinrange(len(balancebase3sequence)):ifbalancebase3sequence[i]1:right.append(i)elifbalancebase3sequence[i]-1:left.append(i)elifbalancebase3sequence[i]0:continueelse:raiseValueError(Invalid Balance Base 3 Sequence!)returnleft,rightif__name____main__:targetint(input())l,rLeftVsRight(ToBalance3(target))print(len(l),end )foriinrange(len(l)):print(pow(3,l[i]),end )print()print(len(r),end )foriinrange(len(r)):print(pow(3,r[i]),end )(2) C#usingSystem.Numerics;usingstaticSystem.Numerics.BigInteger;usingSystem.Collections.Generic;namespaceP7649{publicclassP7649{publicstaticListintBalanceBase3(BigIntegerdecimal_value){BigIntegercurrentdecimal_value;// 将十进制大整数转化为普通三进制, 下标小的是低位下标大的是高位Listintbase3newListint();while(current0){base3.Add((int)(current%3));current/3;}// 最高位补一个0防止出现数组越界base3.Add(0);// 将普通三进制转化为平衡三进制for(inti0;ibase3.Count-1;i){// 某一位是2这一位变成-1然后高位进1if(base3[i]2){base3[i]-1;base3[i1]1;}// 某一位因为刚才进位变成3也需要进位同时这一位变成0if(base3[i]3){base3[i]0;base3[i1]1;}}returnbase3;}publicstaticvoidMain(string[]args){string?valueConsole.ReadLine();if(valuenull)return;BigIntegerxBigInteger.Parse(value);Listintbalance3BalanceBase3(x);// 左盘区和右盘区Listintleft_containernewListint();Listintright_containernewListint();// 平衡三进制某一位为-1就将对应的砝码放在左盘区否则放在右盘区for(inti0;ibalance3.Count;i){if(balance3[i]1)right_container.Add(i);elseif(balance3[i]-1)left_container.Add(i);}Console.Write(left_container.Count );for(inti0;ileft_container.Count;i)Console.Write(BigInteger.Pow(3,left_container[i]) );Console.WriteLine();Console.Write(right_container.Count );for(inti0;iright_container.Count;i)Console.Write(BigInteger.Pow(3,right_container[i]) );}}}
P7649 [BalticOI 2004] Scales (Day1) 题解
发布时间：2026/5/22 22:59:25
P7649 [BalticOI 2004] Scales (Day1)Link: https://www.luogu.com.cn/problem/P7649题目描述给您一个平衡的臂秤一组砝码和一个物体。这些砝码的重量为1 , 3 , 9 , 27 , 81 , … 1, 3, 9, 27, 81, \dots1,3,9,27,81,…即每个砝码的重量为3 33的幂对于每个整数k ≥ 0 k \ge 0k≥0正好有一块砝码重量3 k 3^k3k。物体的重量是m mm其中m mm是正整数。你的任务是把物体放在左边的秤盘上然后把一些砝码放在左右一个或两个秤盘上使得秤平衡。输入格式第一行包含一个整数m mm。输出格式第一行包含有关放在左秤盘上砝码的信息第一个数字必须为非负整数――放在左秤盘上的砝码个数然后是各砝码重量且按递增顺序数字必须用单个空格分隔。第二行包含与第一行相同格式的有关放置在右秤盘上的砝码的信息。输入输出样例 #1输入 #142输出 #13 3 9 27 1 81输入输出样例 #2输入 #230输出 #20 2 3 27说明/提示数据规模与约定对于100 % 100 \%100%的数据1 ≤ m ≤ 10 100 1 \le m \le 10^{100}1≤m≤10100。题目说明来源于 Baltic Olympiad in Informatics 2004 的 Day 1:SCALES。Solution1. 题意本题的题目背景是使用砝码称量物体质量所有砝码的质量皆为3 33的整数次幂次。现在要求对于一块质量已知放在左盘区的物体如何在左右盘中合理放置这些砝码使得天平平衡。2. 分析首先是托盘天平的读数方法。当物块放在左边放置砝码使得天平平衡那么用右边的砝码总质量减去左边砝码的总质量差值就是物块的质量。由此我们容易想到对于一个砝码如果放在右边就记为正值放在左边记为负值那么本题即可转化为将给定正整数转化为一些3 33的幂次的和减去另一些3 33的幂次的差。上面这个过程的核心原理是平衡三进制。将初始输入的十进制值转化为平衡三进制即可求解。平衡三进制是一种使用− 1 , 0 , 1 -1,0,1−1,0,1三个数码的计数体系。为书写方便一般会使用字母Z \text{Z}Z表示− 1 -1−1的数位。例如对于平衡三进制下的( 1 Z 101 ) balance3 (1\text{Z}101)_\text{balance3}(1Z101)balance3化为十进制的结果是( 1 Z 101 ) balance3 1 × 3 4 ( − 1 ) × 3 3 1 × 3 2 0 × 3 1 1 64 (1\text{Z}101)_\text{balance3}1\times3^4(-1)\times3^31\times3^20\times3^1164(1Z101)balance31×34(−1)×331×320×31164从上面的结果很容易看出64 6464被拆分为了81 , − 27 , 9 , 1 81,-27,9,181,−27,9,1也就是说将27 2727和质量为64 6464的物体放在左侧将81 , 9 , 1 81,9,181,9,1放在右侧即可平衡。参考[1] AT_past202107_g 题解[2] 平衡三进制 on OI-wiki[3] 平衡三进制3. 代码(1) Python# 将十进制转化为平衡三进制defToBalance3(decimal_value:int):currentdecimal_value resultlist()whilecurrent:result.append(current%3)current//3result.append(0)foriinrange(len(result)-1):ifresult[i]2:result[i]-1result[i1]1ifresult[i]3:result[i]0result[i1]1returnresult# 将平衡三进制按照±1划分为左右部分defLeftVsRight(balancebase3sequence:list):leftlist()rightlist()foriinrange(len(balancebase3sequence)):ifbalancebase3sequence[i]1:right.append(i)elifbalancebase3sequence[i]-1:left.append(i)elifbalancebase3sequence[i]0:continueelse:raiseValueError(Invalid Balance Base 3 Sequence!)returnleft,rightif__name____main__:targetint(input())l,rLeftVsRight(ToBalance3(target))print(len(l),end )foriinrange(len(l)):print(pow(3,l[i]),end )print()print(len(r),end )foriinrange(len(r)):print(pow(3,r[i]),end )(2) C#usingSystem.Numerics;usingstaticSystem.Numerics.BigInteger;usingSystem.Collections.Generic;namespaceP7649{publicclassP7649{publicstaticListintBalanceBase3(BigIntegerdecimal_value){BigIntegercurrentdecimal_value;// 将十进制大整数转化为普通三进制, 下标小的是低位下标大的是高位Listintbase3newListint();while(current0){base3.Add((int)(current%3));current/3;}// 最高位补一个0防止出现数组越界base3.Add(0);// 将普通三进制转化为平衡三进制for(inti0;ibase3.Count-1;i){// 某一位是2这一位变成-1然后高位进1if(base3[i]2){base3[i]-1;base3[i1]1;}// 某一位因为刚才进位变成3也需要进位同时这一位变成0if(base3[i]3){base3[i]0;base3[i1]1;}}returnbase3;}publicstaticvoidMain(string[]args){string?valueConsole.ReadLine();if(valuenull)return;BigIntegerxBigInteger.Parse(value);Listintbalance3BalanceBase3(x);// 左盘区和右盘区Listintleft_containernewListint();Listintright_containernewListint();// 平衡三进制某一位为-1就将对应的砝码放在左盘区否则放在右盘区for(inti0;ibalance3.Count;i){if(balance3[i]1)right_container.Add(i);elseif(balance3[i]-1)left_container.Add(i);}Console.Write(left_container.Count );for(inti0;ileft_container.Count;i)Console.Write(BigInteger.Pow(3,left_container[i]) );Console.WriteLine();Console.Write(right_container.Count );for(inti0;iright_container.Count;i)Console.Write(BigInteger.Pow(3,right_container[i]) );}}}
