PUZZLEUP 2014

peter1166

newkid 发表于 2014-11-17 09:32
你把SQL写出来就发章。
我写的是这样，感觉还是有点啰嗦：

我的是这样的， 有点啰嗦， 没好意识贴出来。


WITH T AS ( -- 做 3 * 3 的 9个块儿
           SELECT X,Y,ROWNUM V
           FROM (SELECT LEVEL X FROM DUAL CONNECT BY LEVEL <= 3 ) T1
                ,(SELECT LEVEL Y FROM DUAL CONNECT BY LEVEL <= 3 ) T2
          )
    ,T1 AS ( -- 做出所有子块儿
            SELECT SYS_CONNECT_BY_PATH(V,',') P
            FROM T
            CONNECT BY NOCYCLE LEVEL <=3 AND ((X = PRIOR X+1 AND Y = PRIOR Y) OR (Y = PRIOR Y+1 AND X= PRIOR X) OR (Y = PRIOR Y-1 AND X= PRIOR X))
           )
    ,T2 AS ( -- 子块儿去重
            SELECT P, ROW_NUMBER()OVER(ORDER BY P) RN
            FROM (
                  SELECT LISTAGG(VAL,'')WITHIN GROUP(ORDER BY VAL) P
                  FROM (
                        SELECT T1.P ,REGEXP_SUBSTR(P,'[^,]',1,LEVEL) VAL
                        FROM T1
                        CONNECT BY LEVEL <= REGEXP_COUNT(P,',') AND P = PRIOR P AND PRIOR DBMS_RANDOM.value IS NOT NULL
                       )
                  GROUP BY P
                )
           GROUP BY P
           )
SELECT *  
FROM ( -- 拼接子块儿
      SELECT SYS_CONNECT_BY_PATH(P,',') P
      FROM T2
      WHERE LEVEL = 4
      CONNECT BY  LEVEL <= 4 AND P > PRIOR P
      START WITH SUBSTR(P,1,1) = '1'
    )
WHERE  LENGTH(REPLACE(P,',','')) = 9
AND REGEXP_COUNT(P,'1') = 1
AND REGEXP_COUNT(P,'2') = 1
AND REGEXP_COUNT(P,'3') = 1
AND REGEXP_COUNT(P,'4') = 1
AND REGEXP_COUNT(P,'5') = 1
AND REGEXP_COUNT(P,'6') = 1
AND REGEXP_COUNT(P,'7') = 1
AND REGEXP_COUNT(P,'8') = 1
AND REGEXP_COUNT(P,'9') = 1;
--104

peter1166

newkid 发表于 2014-11-17 09:34
我也写了一个，只试了一半的数据：

假设总共N个人，P对来自同校，要求至少有K对来自同校的配对方法。
...

我的算到12个人已经很慢了， 勉强出来结果。


VAR N NUMBER; -- 总共N个人
VAR P NUMBER; -- P对来自同校
VAR K NUMBER; -- 要求至少有K对来自同校
EXEC N:=12;
EXEC P:=4;
EXEC K:=2;

WITH T AS (
          SELECT CHR(64+LEVEL) N , CEIL(LEVEL/2) T FROM DUAL CONNECT BY LEVEL <= 2*P:
          UNION ALL
          SELECT CHR(64+LEVEL+2*P:  ) N , LEVEL+P: FROM DUAL CONNECT BY LEVEL <= N:-2*P:
          )
   ,T1 AS (  -- 所有可能的配对。
            SELECT T.N N1          -- 对手 A
                   ,PRIOR T.N N2   -- 对手 B
                   ,T.T T1         -- 对手 A 所在 校队
                   , PRIOR T.T T2  -- 对手 B 所在 校队
                   ,CASE WHEN T.T = PRIOR T.T THEN 1 ELSE 0 END T_YN  -- 是否同校， 同校则 1 ，否则 0.
                   ,REPLACE(SYS_CONNECT_BY_PATH(N,','),',','') P -- 配对
            FROM T
            WHERE LEVEL = 2
            CONNECT BY N > PRIOR N AND LEVEL <= 2
          )
    , T2 AS ( -- 本想列出所有可能的对局结果， 但有缺陷， 所以下面又多了个 count判断。
              SELECT T2.*
              FROM (
                      SELECT T2.*
                             ,(SELECT COUNT(DISTINCT SUBSTR(T2.P,LEVEL,1)) FROM DUAL CONNECT BY LEVEL <= N:  ) CNT
                      FROM (
                            SELECT  SYS_CONNECT_BY_PATH(P,',') LT ,REPLACE(SYS_CONNECT_BY_PATH(P,','),',','') P
                                   ,LTRIM(SYS_CONNECT_BY_PATH(T1.T_YN,'+'),'+') T_CNT_LIST
                                   ,DBMS_AW.EVAL_NUMBER(LTRIM(SYS_CONNECT_BY_PATH(T1.T_YN,'+'),'+')) T_CNT
                            FROM T1
                            WHERE LEVEL = N:/2   --  局
                            CONNECT BY LEVEL <= N:/2 AND N2 > PRIOR N2 AND PRIOR T1.N1 NOT IN (T1.N1, T1.N2) AND PRIOR T1.N2 NOT IN (T1.N1, T1.N2)
                            START WITH T1.N2 = 'A'
                           ) T2
                    ) T2
              WHERE T2.CNT = N:
             )
SELECT SUM(CASE WHEN T2.T_CNT = K: THEN 1 ELSE 0 END) T_CNT  -- 要求至少有K对来自同校
       ,COUNT(*) TTL_CNT
FROM T2

-- 468        10395

龙神add

这种题都挺有意思的！

newkid

peter1166 发表于 2014-11-17 18:49
我的算到12个人已经很慢了， 勉强出来结果。

把你最后一个WHEN T2.T_CNT = K: 改成WHEN T2.T_CNT >= K: 答案就是519和我一样了。
你这个效率较低，因为你在递归过程中没有检测重叠，最后不得不用个COUNT DISTINCT。
我用了BITAND保证递归过程中都是不重叠的。

newkid

piliskys 发表于 2014-11-14 13:18
#15
--24个人
with a as (select power(2, rownum-1) rn, rownum rnc from dual connect by rownum d.rn  ...

霹雳哥这个在执行12人的时候比我快，我最早也想这么写，后来自作聪明地分成两组分别递归组合，没想到还不如单组来得快。

newkid

peter1166 发表于 2014-11-17 15:18
我的是这样的， 有点啰嗦， 没好意识贴出来。

改用递归WITH和BITAND, 代码会少很多。给你发个章吧，要哪个？

WITH T AS ( -- 做 3 * 3 的 9个块儿
           SELECT X,Y,ROWNUM V
           FROM (SELECT LEVEL X FROM DUAL CONNECT BY LEVEL <= 3 ) T1
                ,(SELECT LEVEL Y FROM DUAL CONNECT BY LEVEL <= 3 ) T2
          )
    ,T1(bits,s,cnt,x,y) AS ( -- 做出所有子块儿
            SELECT POWER(2,v-1),CAST(v AS VARCHAR2(10)),1,x,y FROM t
            UNION ALL
            SELECT bits+POWER(2,v-1),s||v,cnt+1,t.x,t.y
              FROM t1,t
             WHERE cnt<3
                   AND BITAND(bits,POWER(2,v-1))=0
                   AND ((t1.X = t.X+1 AND t1.Y = t.Y) OR (t1.Y = t.Y+1 AND t1.X= t.X) OR (t1.Y = t.Y-1 AND t1.X= t.X))
            )                  
    ,tt AS (SELECT bits,MIN(s) s FROM t1 GROUP BY bits)
,t2(bits,s,cnt,last_s) AS (
SELECT bits,s,1,s FROM tt
UNION ALL
SELECT t2.bits+tt.bits,t2.s||','||tt.s,t2.cnt+1,tt.s
FROM t2,tt
WHERE BITAND(tt.bits,t2.bits)=0 AND tt.s>t2.last_s AND t2.cnt<4
)
SELECT s FROM t2 WHERE cnt=4 AND bits=POWER(2,9)-1;

peter1166

newkid 发表于 2014-11-18 05:39
改用递归WITH和BITAND, 代码会少很多。给你发个章吧，要哪个？

WITH T AS ( -- 做 3 * 3 的 9个块儿

谢谢你的指点。 俺也不客气了， 要个奥迪。

newkid

奥迪已转。

顺便贴个优化过的15题，两次递归还是有好处的，现在不到1秒。同样的人数按霹雳哥写法大约4秒。

WITH all_pairs AS
(SELECT N1,N2,CASE WHEN CEIL(N1/2)=CEIL(N2/2) AND N2/2<=:P THEN 1 ELSE 0 END AS SAME_SCHOOL
       ,BIT1+BIT2 bits
  FROM (SELECT LEVEL N1,POWER(2,LEVEL-1) BIT1 FROM DUAL CONNECT BY LEVEL<=:N)
      ,(SELECT LEVEL N2,POWER(2,LEVEL-1) BIT2 FROM DUAL CONNECT BY LEVEL<=:N)
WHERE N1<N2
)
,same_pairs as (SELECT * FROM all_pairs WHERE SAME_SCHOOL=1)
,same_comb(s,bits,cnt,last_n1) AS (
SELECT CAST(N1||','||N2 AS VARCHAR2(100)),bits,1,N1
  FROM same_pairs
UNION ALL
SELECT s||'|'||N1||','||N2,same_comb.bits+same_pairs.bits,cnt+1,same_pairs.N1
  FROM same_comb,same_pairs
WHERE N1>LAST_N1 AND CNT<:k
)
,comb(s,bits,cnt,last_n1,last_flag) AS (
SELECT CAST(s AS VARCHAR2(100)),bits,cnt,last_n1,1
  FROM same_comb WHERE cnt=:k
UNION ALL
SELECT s||'|'||N1||','||N2,comb.bits+all_pairs.bits,cnt+1,all_pairs.N1,all_pairs.same_school
  FROM comb,all_pairs
WHERE CNT<:N/2
       AND BITAND(comb.bits,all_pairs.bits)=0
       AND (last_flag=all_pairs.same_school AND N1>LAST_N1
            OR last_flag=1 AND all_pairs.same_school=0
           )
)
SELECT COUNT(*) FROM comb WHERE cnt=:N/2 ;

newkid

#17 Coin Game

You will play a game by tossing a fair coin 9 times. Whenever a sequence of two heads following a tail (…THH…) is obtained you will get 1 point. (Maximum point for a game is therefore 3). If you play this game many times what will be the average of your points?

Note:If needed, use three digits after the decimal point.

投币游戏

你玩一个游戏，将一个公平的硬币投掷9次。每当得到一次反面紧跟着两次正面（...THH...）的顺序，你会得到1分。（因此每个游戏最多得3分）。 如果你玩这个游戏很多次，平均分是多少？

注：如果需要的话，精确到小数点后三位数字。

这题太容易了，不能发章。

peter1166

#17     
不发章也得做啊， 看大伙儿能写出几种方法， 想到了4种， 第5个再尝试中。。。