Puzzleup 2013挑战赛即将开始

newkid

〇〇 发表于 2013-7-25 21:37
plsql挑战里每周有个逻辑题，和这差不多，怎么不翻译了？

没什么人关注，就没继续了。其实那个题目更有意思的是写作弊程序，或者写自动猜测程序，我自己搞过了只是没有公开。

呆呆笨笨的鱼

newkid 发表于 2013-7-25 21:34
你的方法就是我前面提到的方法。
这是个什么活动？就是没事闹着玩，可以看看前两年的贴：
http://www.i ...

这个题方法有多种
也可以
第一次称：一边4个
平衡   即两边是  XXYY = XXYY  ，  随便选一边，一边放两个 称第二次 ：平衡即 XY = XY 问题解决                                                                                                    不平衡  XX ≠ YY 每边取一个问题解决

第一次不平衡： （1）XXXX ≠ YYYY ：随便去一边称第二次  结果必然是平衡的 ，从一次分的两边各取一个，问题解决

                     （2） XXXY ≠ YYYX ：随便去一边称第二次   结果必然是  XX ≠ XY  或者  YY≠ XY ，问题解决

解释下（2）：因为不知道X与Y哪个重，所以  第一次称后 重的一边(重重重轻)，  所以 第二次去重的一边称  结果必然是 重重 > 轻重  ，去轻的一边即为XY球
                                                                             轻的一边（轻轻轻重） 同理取重的一边即为XY球

newkid

呆呆笨笨的鱼 发表于 2013-7-26 09:39
这个题方法有多种
也可以
第一次称：一边4个

最后利用轻重结果的方法很巧妙。

weixinchao2012

这个题隐含，X,Y重量不等。
随机分成4,4。第一次称重则有2中结果：
1），平衡。拿天平随便一端，分成2,2，第二次称重，可能有，平衡，与不平衡，平衡的话，就可以拿天平一端的2个就是质量不等的2个球。不平衡的话，天平左右各那一个。
2），不平衡，在天平2端各取2球，分成2,2，同一。
答案：二次。

newkid

#2 Coins
In a country circulating coins exist in denominations of 1u (unit), 5u, 10u, 20u, 25u, 50u, and 100u. Your goal is to select X of these coins to make exactly 100u. What is the smallest value of X that makes it impossible to reach your goal?

Note: X > 0
硬币：有一个国家流通硬币面额为1u,5u,10u,20u,25u,50u和100u(u是货币单位). 你的目标是选出X个硬币刚好凑成100u. X最小为多少, 才能使得你的目标无法达到？

这个用SQL暴力很容易。

udfrog

newkid 发表于 2013-7-31 22:06
#2 Coins
In a country circulating coins exist in denominations of 1u (unit), 5u, 10u, 20u, 25u, 50u ...

感觉这个可以分成1， 5 10 20， 25 50 100三组，用sql求出1-100的所有可能值，性能也该很好

newkid

哪里用那么麻烦，就是笛卡尔积嘛，一下子就算出来了：
SELECT LEVEL N FROM DUAL WHERE LEVEL>1 CONNECT BY LEVEL<=100
MINUS
SELECT DISTINCT C5+C10+C20+C25+C50+100-(5*C5+10*C10+20*C20+25*C25+50*C50)
  FROM (SELECT LEVEL-1 c5  FROM DUAL CONNECT BY LEVEL-1<=20)
      ,(SELECT LEVEL-1 c10 FROM DUAL CONNECT BY LEVEL-1<=10)
      ,(SELECT LEVEL-1 c20 FROM DUAL CONNECT BY LEVEL-1<=5)
      ,(SELECT LEVEL-1 c25 FROM DUAL CONNECT BY LEVEL-1<=4)
      ,(SELECT LEVEL-1 c50 FROM DUAL CONNECT BY LEVEL-1<=2)
WHERE 5*C5+10*C10+20*C20+25*C25+50*C50<=100
ORDER BY 1;


        N
---------
       85
       86
       89
       90
       93
       94
       95
       97
       98
       99      

〇〇

newkid 发表于 2013-7-31 22:06
#2 Coins
In a country circulating coins exist in denominations of 1u (unit), 5u, 10u, 20u, 25u, 50u ...

100个可以，99个就不行，因为全1不够，98个1+1个5太多

udfrog

newkid 发表于 2013-7-31 23:25
哪里用那么麻烦，就是笛卡尔积嘛，一下子就算出来了：
SELECT LEVEL N FROM DUAL WHERE LEVEL>1 CONNECT B ...

嗯，刚开始怕性能不行，也没仔细算下数据量，土鳖了。
写了个plsql的，plsql水平太差了，啥也不知道，一顿查。。。
declare
cnt int:=0;
type nt is table of pls_integer;
v_nt    nt;
begin
    select  rownum
    bulk collect into v_nt
    from    dual
    connect by rownum<=100;
    for i100 in 0..1 loop
        for i50 in 0..(100-100*i100)/50 loop
            for i25 in 0..(100-100*i100-50*i50)/25 loop
                for i20 in 0..(100-100*i100-50*i50-25*i25)/20 loop
                    for i10 in 0..(100-100*i100-50*i50-25*i25-20*i20)/10 loop
                        for i5 in 0..(100-100*i100-50*i50-25*i25-20*i20-10*i10)/5 loop
                            v_nt.delete(100-100*i100-50*i50-25*i25-20*i20-10*i10-5*i5+i5+i10+i20+i25+i50+i100);
                        end loop;
                    end loop;
                end loop;
            end loop;
        end loop;
    end loop;
    dbms_output.put_line(v_nt.first);
end;
/

〇〇

〇〇 发表于 2013-8-1 09:18
100个可以，99个就不行，因为全1不够，98个1+1个5太多

96可以=95*1+1*5
95又不行了
。。