【进制】招待

题目描述

请了两位奆老来为自己种树，小X也稍稍有些不好意思了，于是他准备了一些零食和饮料来招待奆老们。
然而，小X有强迫症，他希望自己和好基友们所有的零食和饮料的质量都要完全相同。
由于小X是一个奆老，所以他看不起普通商店里卖的电子秤，他决定自己做一个。
他的称重工具是一架由金子制成的天平，这架天平的精度非常高，可以达到纳克的标准，1g=109ng，小X会把物品放在天平的右侧，然后在天平的左侧和右侧都放上一些砝码，直至天平平衡。该天平的砝码是用钻石制成的，每个砝码的质量依次为1ng、3ng、9ng、27ng、81ng……，每个砝码的质量都是3的幂次(如3的6次幂表示为3^6=729)，且各不相同。
由于小X是一个奆老，他有对各个物品未卜先知的能力，他会告诉你他的物品的质量，希望你给他一个方案，使得天平的两侧平衡。

输入

输入数据仅有一行包含一个正整数W，表示小X给出的物品的质量，重量单位是纳克(ng)

输出

输出数据共有两行，分别输出左右两端各个砝码及物体的质量，同一行砝码重量必须从小到大排序后按次序输出，第二行的第一个数必须先输出物体的质量，然后才是各个砝码的重量。相邻两个数之间必须严格用一个空格隔开。
注意：输入数据保证一定有解！如有多组解，输出任意一组即可！

样例输入

样例输出

1 3 9 81
67 27

提示

小X给出的物品的质量为67pg，你可以在天平的左边放上4个砝码，重量依次为1,3,9,81总重量94ng，而右边放一个砝码质量为27ng，加上物体的重量67ng，恰好也是94ng，满足题目要求，此时天平的左右两端平衡。

对于20%的数据，W<=100
对于另外20%的数据，W<=10000，最多只用到5个砝码
对于另外20%的数据，W<=1000000，所有砝码都放在左边
对于另外20%的数据，W<=1000000
对于100%的数据，W<=1e15。

【题解】

　　这个题目非常有价值，考察的是三进制的使用，如果把k进行三进制转化，然后

　　1、如果当前为0，则不用管。

　　2、如果当前为1，则在物品对面放当前位置权重的砝码

　　3、如果当前为2，则在物品自己的放当前权重的砝码，同时需要进位。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N = 1000;
 5 ll A[N],B[N];
 6 int a[N];
 7 int cnt = 0 , n , m ;
 8 int main()
 9 {
10     ios_base :: sync_with_stdio(false);
11     cin.tie(NULL) , cout.tie(NULL) ;
12     ll w ;
13     ll p[N];
14     cin >> w ;
15     if( w == 2 ){
16         printf("3\n2 1\n");
17         return 0;
18     }
19
20     p[0] = 1 ;
21     for( int i = 1 ; i <= 33 ; i ++ ){
22         p[i] = p[i-1] * 3 ;
23     }
24     B[m++] = w ;
25
26     while( w ){
27         a[cnt++] = w % 3 ;
28         w /= 3 ;
29     }
30
31     for( int i = 0 ; i <= 33 ; i++ ){
32         if( a[i] == 0 ){
33             continue ;
34         }else if( a[i] == 1 ){
35             A[n++] = p[i] ;
36         }else{
37             B[m++] = p[i] ;
38             a[i] ++ ;
39             int carry = 1 ;
40             for( int j = i + 1 ; j <= 33 ; j++ ){
41                 a[j] += carry ;
42                 if( a[j] == 3 ){
43                     a[j] = 0 ;
44                     carry = 1 ;
45                 }else{
46                     break ;
47                 }
48             }
49         }
50     }
51     for( int i = 0 ; i < n ; i ++ ){
52         printf("%lld%c",A[i],i==n-1?'\n':' ');
53     }
54     for( int i = 0 ; i < m ; i++ ){
55         printf("%lld%c",B[i],i==m-1?'\n':' ');
56     }
57     return 0;
58 }

View Code