CC

自然万物都趋向从有序变得无序

0%

Scales HDU - 3029 (三进制)

发表于 更新于 分类于 Valine：

题目链接:点我

题目

 Give you a scale, a goods weigts m kilograms. And then give you some stones weighting 1, 3, 9, 27, ..., 3^k. Of course, the number of different weights' is only ONE.

Now put the goods on the left of scale. And then you should put some stones on two sides of scale to make the scale balanced. 

An integer m, stands for the weights of the goods (0 ≤ m ≤ 100 000 000)

Output

You should output two lines.

In the first line, the first integer N1 is the number of stones putting on the left of scale, and then N1 integers follow(in the ascend order), indicating the weight of stones putting on the left, seperated by one space. In the second line, please use the same way as the first line's to output the N2, which is the number of stones putting on the right side. Then following N2 integers, which are in ascending order, indicate the stones' weight putting on the right side.

Sample Input

42
30

Sample Output

3 3 9 27
1 81
0
2 3 27

题意:

问天平左右两边个添加多少可以使天平平衡,但添加的数只能是3 ^K,

思路:

三进制,我们知道如果全是三的k 次方相加,那么结果转乘3进制后每一位不是0 就是1 所以我们把输入的数转成三进制,然后它是二的数的位置i那里我们需要加一个 3i−13^{i-1},这些数全部放在天平左边,然后我们把得到的三进制数每一位是1的位置 i, 在天平的右边放3i−13^{i-1},于是天平就平衡了,

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

typedef long long LL;
LL p[100];
bool ad[100];
int a[100];
int num;

void init(){
    p[1] = 1LL;
    for(int i = 2; p[i-1]*3 <=1000000000;++i)
        p[i]= p[i-1] * 3LL;
    memset(ad,false,sizeof(ad));
}

void turn(int n){
    num = 0;
    while(n){
        a[++num] = n % 3;
        n /= 3;
    }
}

void add(int k){
    a[k] += 1;
    for(int i = k; i <= num; ++i){
        if (a[i] > 2){
            a[i] = 0;
            a[i+1]++;
            if(i ==num)
                num++;
        }
    }
}

int main(){
    int n;
    init();
    while(scanf("%d", &n) != EOF){
        memset(a,0,sizeof(a));
        turn(n);
        memset(ad,false,sizeof(ad));
        for(int  i = 1; i <= num; ++i)
        if(a[i] == 2){
            ad[i] = true;
            add(i);
        }
        int l = 0;
        for(int i = 1;i <= num;++i)
            if(ad[i])
                ++l;
        printf("%d", l);
        for(int i = 1;i<=num;++i)
            if(ad[i])
            printf(" %lld", p[i]);
        l = 0;
        for(int i = 1; i <= num;++i)
            if(a[i] == 1)
                ++l;
        printf("\n%d",l);
         for(int i = 1; i <= num;++i)
            if(a[i] == 1)
                printf(" %lld",p[i]);
        printf("\n");
    }
    return 0;
}