HNU 13073 Ternarian Weights 解题报告

本题大意:

用天平对一物品进行称重,现有重量不同的砝码,砝码的重量分别为:1,3,9,27,..,3^n。(n<20)

天平的右侧放砝码,左侧放物品或物品和砝码,使得左右两边的重量相等。

现有一个物品,计算左右两边应当分别放多少个多大的砝码才能使得天平平衡。

例如:现在有一个重量为21的物品,当左侧放物品和重量为9的砝码,右边放重量为27和3的砝码时,天平平衡。

Sample Input
4
2
3
21
250
Sample Output
left pan: 1
right pan: 3

left pan:
right pan: 3

left pan: 9
right pan: 27 3

left pan: 3
right pan: 243 9 1

解题思路

1、首先计算3^i(0<=i<20),然后将计算结果保存至数组st[],数组add[i]=st[0]+st[1]+st[2]+..+st[i]。

2、创建两个数组,left[]保存左侧需要添加的砝码,right[]保存右侧需要删除得砝码。

3、获得大于物品重量的最小add[i]。这是右侧需要的最多得砝码数。

4、计算右侧砝码数与物品重量之差。并找出小于重量之差的最大砝码。

5、如果天平右侧已经没有上一步找出的最大砝码,则在天平的左侧添加此砝码,否则,删除天平右侧中上一步找出得最大砝码。

6、此时,如果天平平衡则退出,若不平衡,则将天平两端的重量之差减去上一步添加或删除的砝码。然后返回第4步。

具体代码如下:

#include <stdio.h>
#include <string.h>
#define MAX 1009
//st[i]=3^i, add[i]=st[0]+st[1]++st[i];
long st[20], add[20];
void init()
{
    int i;
    st[0] = 1;
    add[0] = 1;
    for(i=1; i<20; i++)
    {
        st[i] = st[i-1]*3;
        add[i] = add[i-1]+st[i];
    }
}
int find(int v)        //在st数组中,找出小于V的最大数
{
    int i;
    for(i=0; i<20; i++)
        if(v < st[i])
            return i-1;
}
int main()
{
    int n, i, hel, tmp, num, num1, num2;
    long left[20],right[20];
    long w;
    init();
    scanf("%d",&n);
    while(n--)
    {
        memset(left,0,sizeof(left));
        memset(right, 0, sizeof(right));

        scanf("%ld",&w);
        for(i=0; i<20; i++)
        {
            if(w < add[i])
                break;
        }
        num = i;
        num1=0;        //左边砝码得个数
        num2=i;        //右边砝码得个数
        hel = add[i]-w;
        while(hel != 0)        //hel==0时, 两端平衡
        {
            //if(hel == 1)
                //break;

            tmp = find(hel);    //找出小于hel的最大砝码
            if(right[tmp] != 0)    //右边已删除此砝码
            {
                left[tmp] = st[tmp];
                hel = hel-left[tmp];
                num1++;
            }
            else
            {
                right[tmp] = st[tmp];
                hel = hel-right[tmp];
                num2--;
            }
        }
    //    if(hel == 1 && right[0])
    //    if(hel != 0)
    //    {
    //        left[0] = hel;
    //    }
        printf("left pan:");
        for(i=num; i>=0; i--)
        {
            if(left[i] != 0)
                printf(" %ld",left[i]);
        }
        printf("\nright pan:");
        for(i=num; i>=0; i--)
        {
            if(right[i] == 0)
                printf(" %ld",st[i]);
        }
        printf("\n\n");
    }
    return 0;
}




更多相关文章
  • 题意和解决回路匹配的思路如同hdu3488 (这里我第一次想到最短路,但是对于有回路这个不知道怎么处理,后来看了别人的解题报告才知道KM匹配,但是看到KM之后就自己想...想了很久....还是不知道回路这个地方怎么匹配......其实应该这样来想....总共有N个城市....如果是要形成回路..那么 ...
  • http://poj.org/problem?id=1173 发现此题资料甚少,斗胆第一次写一份解题报告[题意]     输入 n(代表二进制位数) k(代表黑条白条总共有几条,条形码是以黑条开始的,再白黑交替出现) m(代表每条最多占多少个二进制位)     输出这种模式的条形码的有多少个?    ...
  • 题目大意:使用两个哈希表来解决哈希冲突的问题.假如现在有两个哈希表分别为:H1,H2 ,大小分别为:n1,n2:现有一数据X需要插入,其插入方法为: 1.计算index1 = X MOD N1,  若哈希表H1的index1位置没有保存数据,则直接将X保存到H1得index1:否则,若哈希表H1的i ...
  • 题目大意:输入一个偶数(x<32),输出这个偶数是由哪两个素数相加所得. 比如:一个偶数26,它可以是3+23,7+19,13+13,这些素数相加所得. 输入输出样例: Sample Input 3 4 26 100 Sample Output 4 has 1 representation(s ...
  • 好几年没有做ACM了,感觉忘得差不多了,这个做着做着就打瞌睡了!言归正传,下面是我的解题思路: 首先的话,我们可以画一个函数图,以输入数组的下标为X轴,以数组的和为Y轴,当数组和小于零时,我们使用备用的数组和sum2和备用的最小下标min2,并用flag进行标记.具体实现可以参考代码. 需要注意的地 ...
  • 一.原题中文大意. 1      2       3      4       5      6         7     8 9     10       11    12      13     14       15    16 17    18      19    20       21 ...
  • //我是莱鸟,多多交流 //380k //94ms 题目的意思是:每种装备可由多个生产商提供,从每一种装备中选择一个厂家的设备,使得所选的总的各种装备中的最小带宽B与他们的价格之和P的比值B/P达到最大. 解题思路: 准备工作:在输入时,统计所有装备中的最小值min,和每种装备中的最大值max,然后 ...
  • Problem B: Ternarian Weights
    大致题意:使用三进制砝码采取相应的措施衡量出给定的数字主要思路:三进制,如果 大于 2 向前进位,之前一直没写好放弃了,这次终于写好了…… #include <iostream> #include <cstdio> #include <cstdlib> #incl ...
一周排行