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 ...
一周排行
  • 


    		    紙上談兵的JAVA中間件之weblogic(安裝篇)
    经过长时间的摸索与学习,现在终于能够对中间件这个名词有一定概念上的了解,这篇文章也是想幫助
  • CSS命名规则 头:header 内容:content/containe 尾:footer 导航:nav 侧栏:sidebar 栏目:column 页面外围控制整体布局宽度:wrapper 左右中:left righ
  • 定义一个 Actor 类 要定义自己的Actor类,需要继承 Actor 并实现receive 方法. receive 方法需要定义一系列 case 语句(类型为 PartialFunction[Any, Unit]
  • 系统妈 随着Windows 10Build 10074 Insider Preview版发布,有理由相信,Win10离最终RTM阶段已经不远了.看来稍早前传闻的合作伙伴透露微软将在7月底正式发布Win10的消息越来越 ...
  • JDK源碼閱讀(一) ArrayList
    基于JDK7.0 ArrayList<E>类继承了抽象类AbstractLis ...
  • I. Sale in GameStore Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/gym/100513/problem/I
  • http://www.eetop.cn/blog/html/03/3349.html 如果一个图中我们画了n条曲线,但是我们只想加图例说明(legend)的只有m条 (m<n).网上可以搜索很到资料 ...
  • FZU 2147  AB Game
    A-B Game Time Limit:1MS     Memory Limit:3276
  • 有的时候,我们需要将一些Json格式的字符串反序列化为.Net对象,虽然有强大的Json.net可以幫助我们快速完成这一操作.但首先仍需要我们根据Json数据手动编写C#类,这也是一件比较枯燥而容易出错的事情. 今天 ...
  • 很久都没有写驱动代码了,对于一些驱动相关的内核变化也没有怎么关心.这次重游<LDD3>获益良多,其值对于struct file_operations中ioctl的消失也让我长了不少见识. 当年看<L ...