自动搬运

查看原文

来自洛谷，原作者为

	E_D_ZYZE AFOed

搬运于2025-08-24 22:31:52，当前版本为作者最后更新于2021-06-25 19:03:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

推导部分：（高精见代码）

以样例#1为例，将 $(42)_{10}$ 三进制分解为 $(1120)_3$，从低位至高位遍历此数。

1. 第 $i$ 位为 $0$

直接跳过。

2. 第 $i$ 位为 $1$

在右盘放入质量为 $3^{i-1}$ 的砝码。

3. 第 $i$ 位为 $2$

由于每种质量的砝码只有一个，所以不可能同时在右盘放入两个质量为 $3^{i-1}$ 的砝码。解决方案：在左盘放入 $3^{i-1}$ 的砝码，在右盘放入 $3^{i}$ 的砝码，此时即相当于在右盘放入 $3^{i}-3^{i-1}=2\times 3^{i-1}$ 的砝码。

具体做法：在左盘放入质量为 $3^{i-1}$ 的砝码，并使 $i+1$ 位加 $1$（$i+1$ 位之后一并处理即可）。

4. 第 $i$ 位为 $3$

第 $i-1$ 位进位后可能得到第 $i$ 位为 $3$ 的情况，直接向 $i+1$ 位再次进位即可。

code:

#include <bits/stdc++.h>
using namespace std;

struct node //专门处理 3 的幂用 
{
	int t[ 105 ] , len;
	
	node()
	{
		memset( t , 0 , sizeof t );
		t[ 1 ] = 1;
		len = 1;
	}

	void tim() //乘 3 
	{
		for( int i = 1 ; i <= len ; i ++ )
			t[ i ] *= 3;
		for( int i = 1 ; i <= len ; i ++ )
			t[ i + 1 ] += t[ i ] / 10 , t[ i ] %= 10;
		if( t[ len + 1 ] > 0 )
			len ++;
	}
	
	void print() //输出 
	{
		for( int i = len ; i >= 1 ; i -- )
			printf( "%d" , t[ i ] );
		putchar( ' ' );
	}
};

vector< int > a; //保存三进制的原数 
vector< node > l , r; //保存左右盘中的砝码 

char c[ 105 ];
int len;

int div() //计算商，返回余数 
{
	int t , num = 0;
	for( int i = 1 ; i <= len ; i ++ )
	{
		t = ( num + c[ i ] ) % 3;
		c[ i ] = ( num + c[ i ] ) / 3;
		num = t * 10;
	}
	return t;
}

bool ept()
{
	for( int i = 1 ; i <= len ; i ++ )
		if( c[ i ] > 0 )
			return false;
	return true;
}

void input() //读入高精整数并计算出其三进制的值 
{
	
	scanf( " %s" , c + 1 );
	len = strlen( c + 1 );
	for( int i = 1 ; i <= len ; i ++ )
		c[ i ] -= '0';
	while( ! ept() )
	{
		a.push_back( div() );
	}
	a.push_back( 0 );
}

signed main()
{
	input();
	
	node base;
	for( int i = 0 ; i < a.size() ; i ++ ) //见上文推导过程 
	{
		if( a[ i ] == 3 )
		{
			a[ i ] = 0;
			a[ i + 1 ] ++;
		}
		if( a[ i ] == 2 )
		{
			l.push_back( base );
			a[ i ] = 0;
			a[ i + 1 ] ++;
		}
		if( a[ i ] == 1 )
		{
			r.push_back( base );
		}
		base.tim();
	}
	
	printf( "%d " , l.size() );
	for( int i = 0 ; i < l.size() ; i ++ )
		l[ i ].print();
	printf( "\n%d " , r.size() );
	for( int i = 0 ; i < r.size() ; i ++ )
		r[ i ].print();
	return 0;
}

Thanks for watching.