简单数学推导+高精

E_D_ZYZE · 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.