Puzzleup 2013挑战赛即将开始

newkid

6个盒子的情况，仅有以下组合是可能的：

126=345 (       136大，145小，146大，156大)
136=245 (126小，       145小，146大，156大)
145=236 (126小, 136小,        146大，156大)
146=235 (126小，136小, 145小       ，156大)
156=234 (126小，136小，145小，146小       )

所以6个盒子只需称两次：
第一次，136 vs 245
        136 = 245: 结束
        136 > 245: 126=345 结束
        136 < 245: 称第二次

第二次，146 vs 235
        146 = 235: 结束
        146 > 235: 145=236 结束
        146 < 235: 156=234 结束

newkid

WITH t AS (
SELECT *
FROM (
      SELECT left_str,TRANSLATE('12345678','$'||left_str,'$') AS right_str
        FROM (
      SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') left_str
        FROM (SELECT LEVEL n FROM DUAL CONNECT BY LEVEL<=8)
      WHERE LEVEL=4
       START WITH n=1  ----  SQL生成8个盒子所有可能的情形：令左边包含1号箱
      CONNECT BY LEVEL<=4 AND n > PRIOR n
             )
     )
WHERE SUBSTR(left_str,2,1)>SUBSTR(right_str,2,1)   --- 将两边的盒子排序, 按顺序比较每个盒子，一旦出现左边箱号>右边箱号 则有可能
      OR SUBSTR(left_str,3,1)>SUBSTR(right_str,3,1)
      OR SUBSTR(left_str,4,1)>SUBSTR(right_str,4,1)
)
,t2 AS (
SELECT t1.left_str||'='||t1.right_str eq_str
      ,t2.*
      ,TRANSLATE(t1.left_str,'$'||t2.left_str,'$') diff_s1  ---- t1.left_str 中和 t2.left_str 的不同字符
      ,TRANSLATE(t2.left_str,'$'||t1.left_str,'$') diff_s2  ---- t2.left_str 中和 t1.left_str 的不同字符
  FROM t t1,t t2
WHERE t1.left_str<>t2.left_str
)
,t3 AS (
SELECT t2.*
      ,TRANSLATE(left_str,'$'||diff_s2,'$') AS left_s1   ------ t1.left_str 中 拿掉diff_s1剩下的字符
      ,TRANSLATE(right_str,'$'||diff_s1,'$') AS left_s2  ------ t1.right_str 中 拿掉diff_s2剩下的字符
  FROM t2
)
,t4 as (
SELECT t3.*
      ,CASE WHEN LENGTH(diff_s1)=1     ---- 只有一个被换掉
            THEN CASE WHEN diff_s2>diff_s1 THEN '>' ELSE '<' END
            WHEN LENGTH(diff_s1)=3     ---- 3个被换掉, 剩下的肯定是1, 换掉后肯定变小
            THEN '<'
            --------- 以下为换掉两个的情况
            WHEN SUBSTR(diff_s2,1,1)>SUBSTR(diff_s1,1,1) AND SUBSTR(diff_s2,2,1)>SUBSTR(diff_s1,2,1) THEN '>'  -- 以小换大
            WHEN SUBSTR(diff_s2,1,1)<SUBSTR(diff_s1,1,1) AND SUBSTR(diff_s2,2,1)<SUBSTR(diff_s1,2,1) THEN '<'  -- 以大换小
            WHEN SUBSTR(left_s2,1,1)>SUBSTR(left_s1,1,1) AND SUBSTR(left_s2,2,1)>SUBSTR(left_s1,2,1) THEN '<'  -- 换剩下的右边大于左边
            WHEN SUBSTR(left_s2,1,1)<SUBSTR(left_s1,1,1) AND SUBSTR(left_s2,2,1)<SUBSTR(left_s1,2,1) THEN '>'  -- 换剩下的右边小于左边
            ELSE '*'  --- 无法确定
       END AS r            
  FROM t3
)
SELECT eq_str
      ,LISTAGG(left_str||r||right_str,' ') WITHIN GROUP (ORDER BY left_str)
  FROM t4
GROUP BY eq_str
ORDER BY eq_str;

有这个表之后，再想办法继续。

newkid

〇〇 发表于 2013-9-19 06:53
最轻的为1号, 最重的为8号
还是
最轻的为1斤, 最重的为8斤？

看上下文1,8是箱号，如果是重量应该带有单位。
虽然没有明说，但是可以理解为顺序是从轻到重。要不然给的条件就没有意义。

udfrog

newkid 发表于 2013-9-18 23:42
#9 Eight Boxes
8 boxes each having different weights are numbered from 1 to 8 (the lightest 1, the  ...

You have a balance scale with two pans on which you can compare the weight of two groups each having 4 boxes这句我感觉意思是说托盘上只能每边都放4个，以这样的方式去比较。然后我看到你说6个的情况入手，我觉得歧义来了。然后上去puzzleup网上一看，他们果然针对这句话修正了下，有点不出所料的感觉啊：
Dear PuzzleUp Contenders,

To clarify the meaning, the question text has changed.

Old: "You have a balance scale with two pans on which you can compare the weight of two groups each having 4 boxes."

New: "You have a balance scale with two pans on which you can compare the weight of two groups each having exactly 4 boxes."

Please take notice and submit your answers accordingly.

We wish a pleasant competition to all.

Regards,
PuzzleUp Team

piliskys

newkid 发表于 2013-9-18 23:42
#9 Eight Boxes
8 boxes each having different weights are numbered from 1 to 8 (the lightest 1, the  ...

我怎么觉得这题好容易啊，算法就是先列出有多少组合，这个简单，然后就是二分查找，
with aa as (select rownum rn from dual connect by rownum <9)
select * from (
select a.rn||b.rn||c.rn||d.rn   aa,
replace(replace(replace( replace('12345678',a.rn),b.rn),c.rn),d.rn) bb
from aa a,aa b,aa c,aa d
where a.rn<b.rn
and a.rn=1   --总要放在一边的
and b.rn<c.rn
and c.rn<d.rn
  )
where   case  when   substr(aa,1,1)<substr(bb,1,1) and
                      substr(aa,2,1)<substr(bb,2,1) and
                       substr(aa,3,1)<substr(bb,3,1) and
                        substr(aa,4,1)<substr(bb,4,1)  then 0
                 when   substr(aa,1,1)>substr(bb,1,1) and
                      substr(aa,2,1)>substr(bb,2,1) and
                       substr(aa,3,1)>substr(bb,3,1) and
                        substr(aa,4,1)>substr(bb,4,1)  then 0        else 1 end =1
共有21组， 从11组出发，11-》6-》3-》2 判断到2就是最后了，不相同就是1了，最大深度就是4，

所以，结果就是4，，，
我有些估计是我题意弄错或哪个环节搞错了                     

newkid

udfrog 发表于 2013-9-20 11:49
You have a balance scale with two pans on which you can compare the weight of two groups each havi ...

我不觉得有歧义，你理解有误吧。如果要解8个盒子的题，当然得每边放四个，因为天平并不会告诉你差距有多少，只能告诉你哪边重。

我举6个盒子的例子，是试图从简化的题目中找到解题思路。果然我按同样方法已经找出8个盒子的所有可能性，现在离答案只有一步之遥了，等有空我把剩下的写完。

udfrog

newkid 发表于 2013-9-20 22:37
我不觉得有歧义，你理解有误吧。如果要解8个盒子的题，当然得每边放四个，因为天平并不会告诉你差距有多少 ...

原来你这个6个盒子是这个意思，我本来也奇怪，你既然括号4个盒子，怎么又搞出6个盒子来了。。最近几天痴迷游泳，因为前几天刚刚学会，哈哈我就是传说中套着游泳圈学会的~~~

udfrog

piliskys 发表于 2013-9-20 22:34
我怎么觉得这题好容易啊，算法就是先列出有多少组合，这个简单，然后就是二分查找，
with aa as (select ...

嗯，到21组这里是比较容易，问题是2分法不适用，起码应该不能11-》6-》3-》2这么用，因为你根本没有这些组合的重量排序，你并不知道1368和2458谁重

newkid

目前只搞出了7次的做法。不知道有没有更少的。

SEQ	ATTEMPTS	IF_MORE	IF_LESS
1	1368 vs 2457
2	1368<2457,1468 vs 2357
3	1368<2457,1468<2357,1478 vs 2356
4	1368<2457,1468<2357,1478<2356,1578 vs 2346		1678
5	1368<2457,1468<2357,1478<2356,1578>2346,1567 vs 2348		1568
4	1368<2457,1468<2357,1478>2356,1568 vs 2347
5	1368<2457,1468<2357,1478>2356,1568<2347,1378 vs 2456	1278
5	1368<2457,1468<2357,1478>2356,1568>2347,1378 vs 2456		1567
6	1368<2457,1468<2357,1478>2356,1568>2347,1378>2456,1278 vs 3456	1567	1567
3	1368<2457,1468>2357,1457 vs 2368
4	1368<2457,1468>2357,1457<2368,1567 vs 2348
5	1368<2457,1468>2357,1457<2368,1567<2348,1378 vs 2456		1458
6	1368<2457,1468>2357,1457<2368,1567<2348,1378>2456,1458 vs 2367	1278	1278
5	1368<2457,1468>2357,1457<2368,1567>2348,1278 vs 3456
6	1368<2457,1468>2357,1457<2368,1567>2348,1278<3456,1458 vs 2367
7	1368<2457,1468>2357,1457<2368,1567>2348,1278<3456,1458<2367,1378 vs 2456	1467	1467
7	1368<2457,1468>2357,1457<2368,1567>2348,1278<3456,1458>2367,1467 vs 2358	1378	1378
6	1368<2457,1468>2357,1457<2368,1567>2348,1278>3456,1458 vs 2367	1467	1467
4	1368<2457,1468>2357,1457>2368,1378 vs 2456	1278	1456
2	1368>2457,1358 vs 2467
3	1368>2457,1358<2467,1367 vs 2458
4	1368>2457,1358<2467,1367<2458,1278 vs 3456
5	1368>2457,1358<2467,1367<2458,1278<3456,1467 vs 2358	1458
6	1368>2457,1358<2467,1367<2458,1278<3456,1467<2358,1567 vs 2348	1458	1458
5	1368>2457,1358<2467,1367<2458,1278>3456,1567 vs 2348
6	1368>2457,1358<2467,1367<2458,1278>3456,1567<2348,1268 vs 3457	1458	1458
6	1368>2457,1358<2467,1367<2458,1278>3456,1567>2348,1458 vs 2367
7	1368>2457,1358<2467,1367<2458,1278>3456,1567>2348,1458<2367,1467 vs 2358	1268	1268
7	1368>2457,1358<2467,1367<2458,1278>3456,1567>2348,1458>2367,1467 vs 2358	1268	1268
4	1368>2457,1358<2467,1367>2458,1268 vs 3457	1267	1278
3	1368>2457,1358>2467,1258 vs 3467
4	1368>2457,1358>2467,1258<3467,1268 vs 3457
5	1368>2457,1358>2467,1258<3467,1268<3457,1348 vs 2567	1278
6	1368>2457,1358>2467,1258<3467,1268<3457,1348<2567,1278 vs 3456	1567	1567
5	1368>2457,1358>2467,1258<3467,1268>3457,1567 vs 2348		1348
4	1368>2457,1358>2467,1258>3467,1248 vs 3567	1238
5	1368>2457,1358>2467,1258>3467,1248<3567,1567 vs 2348		1348

newkid

找出21种可能答案只是最简单的一部，接下来就是找这些答案之间的关系。比如，假设答案为1238=4567, 那么可以推理出其他的20个不等式：

1248>3567
1258>3467
1267<3458
1268>3457
1278>3456
1348>2567
1358>2467
1367<2458
1368>2457
1378>2456
1456<2378
1457<2368
1458>2367
1467<2358
1468>2357
1478>2356
1567<2348
1568>2347
1578>2346
1678>2345

假如答案为1458=2367, 则可以推出以下26个不等式（之所以不是20个，是因为某些关系同时可能存在，比如1268<3457和1268>3457）

1238<4567
1248<3567
1258<3467
1267<3458
1268<3457
1268>3457
1278<3456
1278>3456
1348<2567
1358<2467
1367<2458
1368<2457
1368>2457
1378<2456
1378>2456
1456<2378
1457<2368
1467<2358
1467>2358
1468>2357
1478>2356
1567<2348
1567>2348
1568>2347
1578>2346
1678>2345

把这些关系全部构造出来之后，就要试图找一棵树使得它的高度尽可能低。方法是考察每一个猜测对象，如果“大于”可能的答案有多少，如果“小于”可能的答案有多少，这两个数之中取较大的作为“最坏情况”。把“最坏情况”最低的做为下一步的猜测对象。然后对所有分支重复同样的操作。
因为没办法穷尽所有的猜测，这个答案也只能是近似的，看看有没有人能够从数学上证明。