PUZZLEUP 2017

lugionline

还有其它的吗？

newkid

lugionline 发表于 2017-11-28 08:23
还有其它的吗？

我疏忽了，最后变形完毕，忘记两个三角形再交换位置了。确实是25种。


with c as ( ---- 9个点及其坐标
select x,y,row_number() OVER(ORDER BY x,y) cid
  from (select level x from dual connect by level<=3)
      ,(select level y from dual connect by level<=3)
)
,m as ( ----- 两两的点构成的线段, 两个端点命名为A和B
select c1.x A_x,c1.y A_y,c2.x B_x,c2.y B_y
      ,c1.cid||c2.cid mid
  from c c1,c c2
WHERE c1.cid<c2.cid
)
,crossing AS ( ----- 所有交叉的成对线段
SELECT m1.mid cr1,m2.mid cr2
  FROM m m1,
       (SELECT mid,A_x C_x,A_y C_y,B_x D_x,B_y D_y FROM m) m2 ---- 第一个线段AB，第二个线段改名CD, 方便套用算法
WHERE m1.mid<>m2.mid
       AND ((C_x-A_x)*(D_y-A_y)-(D_x-A_x)*(C_y-A_y))*((C_x-B_x)*(D_y-B_y)-(D_x-B_x)*(C_y-B_y))<=0
       AND ((A_x-C_x)*(B_y-C_y)-(B_x-C_x)*(A_y-C_y))*((A_x-D_x)*(B_y-D_y)-(B_x-D_x)*(A_y-D_y))<=0
)
,tr AS ( ---- 所有三角形及其三条边
SELECT c1.cid||c2.cid||c3.cid as tid
      ,c1.cid||c2.cid mid1
      ,c1.cid||c3.cid mid2
      ,c2.cid||c3.cid mid3
  FROM c c1,c c2,c c3
WHERE c1.cid<c2.cid
       AND c2.cid<c3.cid
       AND (c2.y-c1.y)*(c3.x-c1.x)<>(c3.y-c1.y)*(c2.x-c1.x)
)
,trm AS ( ---- 每个三角形拆成三行，一条边一行
SELECT tid,DECODE(n,1,mid1,2,mid2,3,mid3) mid
  FROM tr,(SELECT LEVEL n FROM DUAL CONNECT BY LEVEL<=3)
)
,ctrm AS (---所有交叉或触碰的成对三角形
SELECT DISTINCT trm1.tid tid1,trm2.tid tid2
  FROM trm trm1,trm trm2,crossing
WHERE trm1.tid<trm2.tid
       AND trm1.mid=crossing.cr1
       AND trm2.mid=crossing.cr2
)
,p as (
SELECT tr1.tid||tr2.tid s
  FROM tr tr1,tr tr2         
WHERE tr1.tid<tr2.tid
MINUS
SELECT tid1||tid2 FROM ctrm
)
,p2 as (
SELECT s
      ,SUBSTR(s2,1,1) c1
      ,SUBSTR(s2,2,1) c2
      ,SUBSTR(s2,3,1) c3
      ,SUBSTR(s2,4,1) c4
      ,SUBSTR(s2,5,1) c5
      ,SUBSTR(s2,6,1) c6
FROM (
SELECT s,TRANSLATE(s,'123456789',tpl) s2
FROM p
    ,(SELECT '123456789' tpl FROM DUAL
     UNION ALL SELECT '321654987' FROM DUAL
     UNION ALL SELECT '789456123' FROM DUAL
     UNION ALL SELECT '987654321' FROM DUAL
     UNION ALL SELECT '147258369' FROM DUAL
     UNION ALL SELECT '963852741' FROM DUAL
     UNION ALL SELECT '741852963' FROM DUAL
     UNION ALL SELECT '369258147' FROM DUAL
     )
)
)
SELECT DISTINCT MIN(s4)
  FROM (
SELECT s,decode(n,1,s3,substr(s3,4)||substr(s3,1,3)) s4
  FROM (
SELECT s
      ,LEAST(c1,c2,c3)||DECODE(LEAST(c1,c2,c3),c1,LEAST(c2,c3),C2,LEAST(c1,c3),LEAST(c1,c2))||GREATEST(c1,c2,c3)
     ||LEAST(c4,c5,c6)||DECODE(LEAST(c4,c5,c6),c4,LEAST(c5,c6),C5,LEAST(c4,c6),LEAST(c4,c5))||GREATEST(c4,c5,c6) s3
  FROM p2
   )
  ,(select 1 n from dual union all select 2 from dual) -----两个三角形再交换位置
)
GROUP BY s
;

MIN(S4)
----------------------
125368
125479
125489
127358
124368
124568
124569
125389
127568
126479
124356
126489
124389
124359
124358
127389
125679
124367
125678
124689
126459
126458
127359
124379
126579

25 rows selected.

newkid

#17 FIVE BALLS

Five identical looking balls weigh 1, 2, 3, 4 and 5 grams. You want to find weight of each ball using a digital scale with a single pan by always measuring total weight of 3 balls.

At least how many times you need to measure, in order to guarantee finding the weights of every ball?

五个球外观完全相同，重量为1,2,3,4和5克。你想用找出每个球的重量，用的是一个带有单个托盘的数字天平，每次总是测量3个球的总重量。

至少需要多少次测量才能保证找出每个球的重量？

〇〇

newkid 发表于 2017-11-30 01:32
#17 FIVE BALLS

Five identical looking balls weigh 1, 2, 3, 4 and 5 grams. You want to find weight ...

先找出1，以后把1和其他放一起，平衡就能知道哪个是另一个+1

〇〇

〇〇 发表于 2017-11-30 08:13
先找出1，以后把1和其他放一起，平衡就能知道哪个是另一个+1

最多4次，找出1，方法，每次1边1只，轻的留下
1+a球vsb球，如果平衡(a,b)in (2,3),(3,4),(4,5)

〇〇

在1的基础上，找2，需要3次，再找3需要2次，再找4需要1次，10次可以全找出，现在看能否少

solomon_007

〇〇 发表于 2017-11-30 08:30
最多4次，找出1，方法，每次1边1只，轻的留下
1+a球vsb球，如果平衡(a,b)in (2,3),(3,4),(4,5)

已知 x1 + x2 + x3 + x4 + x5 = 15, 要解开方程，显然还得 4个方程才够啊( 下面随便列一下)

       x1 + x2 + x3                 = a,

               x2 + x3  + x4        = b,

                      x3  + x4   + x5 = c,

      x1           + x3           + x5 =d

〇〇

〇〇 发表于 2017-11-30 09:41
在1的基础上，找2，需要3次，再找3需要2次，再找4需要1次，10次可以全找出，现在看能否少

这就是纯基于比较的冒泡排序算法，要少，还要利用数字之间相等关系

newkid

〇〇 发表于 2017-11-30 08:30
最多4次，找出1，方法，每次1边1只，轻的留下
1+a球vsb球，如果平衡(a,b)in (2,3),(3,4),(4,5)

你这“1边1只"什么意思？
这是个单托盘数字天平，就是能告诉你总克数的，不是两边比大小。
但是有限制一定要三个一起称。
我能证明四次一定能找出来，但是不知道是不是最少。

却早已分离

我觉得3次