puzzleup 2011

newkid

#19 Eight Cubes

You have eight identical unit cubes, each of which is given a different letter.  These eight unit cubes are conjoined to form a 2x2x2 cube.  You will move on these cubes and produce 8-letter codes.

.You can begin your tour on any unit cube.
.You can pass from that cube to any of the neighboring (ie. cubes sharing a common surface) cubes.
.You will visit each unit cube exactly once.

How many different codes you can produce?

你有8个相同的小方块，每个被赋予一个不同的字母。这8个小方块被组合成2X2X2的方块。你在这些方块上移动来产生一个8字母的编码。
你可以从任意一个方块开始。
你可以从这个方块移到任意一个相邻的方块（相邻表示两个方块共享一个面）
每个方块恰好访问一次。

你总共能够产生多少个不同编码？

这里有个隐含前提就是2X2X2的摆放方法是给定的，否则就肯定是8!种了。

WITH data AS (
SELECT 'A' c,'B' n1,'D' n2,'E' n3 FROM DUAL
UNION ALL SELECT 'B','A','C','F' FROM DUAL
UNION ALL SELECT 'C','B','D','G' FROM DUAL
UNION ALL SELECT 'D','A','C','H' FROM DUAL
UNION ALL SELECT 'E','F','H','A' FROM DUAL
UNION ALL SELECT 'F','E','G','B' FROM DUAL
UNION ALL SELECT 'G','F','H','C' FROM DUAL
UNION ALL SELECT 'H','E','G','D' FROM DUAL
)
SELECT COUNT(*)
  FROM data
WHERE LEVEL=8
CONNECT BY NOCYCLE c IN (PRIOR n1,PRIOR n2,PRIOR n3);

  COUNT(*)
----------
       144

newkid

#20 A Number Divisible by 7

XY is a two digit number.  We get a new number by writing the numerals "123456789" to the right of the number XY 99 times. This new number is divisible by 7. When the swap X and Y in this number, its value raises and it continues to be divisible by 7.

What is the number XY?

XY是两位整数，在右边添上"123456789" 共 99 次，得到的新数可以被7整除。XY对调则该数增大，仍然可被7整除。XY是多少？

newkid

20题就是大数除法，用递归WITH或MODEL都可以。

19题我想扩展到N*N*N的立方体，结果N=3就很难出来了：

VAR N NUMBER;
EXEC :N:=3;

WITH cells AS (
SELECT CASE WHEN x BETWEEN 1 AND (:N+1)/2 AND y <=x AND z=1 THEN
                  CASE WHEN x=1 AND y=1 THEN 8      ------ 8个定点
                       WHEN x=(:N+1)/2 AND y=(:N+1)/2 THEN 6  ---------6个面的中心点
                       WHEN x=(:N+1)/2 AND y=1 THEN 12  ---------12条边的中点
                       WHEN x=(:N+1)/2 OR x=y THEN 24  ------ 24条对焦线、中线
                       ELSE 48
                  END
             ELSE 0
        END AS m
       ,x,y,z
   FROM (SELECT LEVEL x FROM DUAL CONNECT BY LEVEL<=:N)
       ,(SELECT LEVEL y FROM DUAL CONNECT BY LEVEL<=:N)
       ,(SELECT LEVEL z FROM DUAL CONNECT BY LEVEL<=:N)
)
SELECT SUM(m*COUNT(*)) total_cnt
  FROM (SELECT CONNECT_BY_ROOT(m) m
         FROM cells
       WHERE LEVEL=:N*:N*:N
       START WITH m>0
       CONNECT BY NOCYCLE (x,y,z) IN ((PRIOR x+1,PRIOR y,PRIOR z),(PRIOR x-1,PRIOR y,PRIOR z),(PRIOR x,PRIOR y+1,PRIOR z),(PRIOR x,PRIOR y-1,PRIOR z),(PRIOR x,PRIOR y,PRIOR z+1),(PRIOR x,PRIOR y,PRIOR z-1))
       )
GROUP BY m;

跑了一个多小时：
TOTAL_CNT
----------
   4960608

Elapsed: 01:18:39.52

用位操作优化一下，跑了半小时：

WITH c AS (
SELECT CASE WHEN x BETWEEN 1 AND (:N+1)/2 AND y <=x AND z=1 THEN
                  CASE WHEN x=1 AND y=1 THEN 8      ------ 8个定点
                       WHEN x=(:N+1)/2 AND y=(:N+1)/2 THEN 6  ---------6个面的中心点
                       WHEN x=(:N+1)/2 AND y=1 THEN 12  ---------12条边的中点
                       WHEN x=(:N+1)/2 OR x=y THEN 24  ------ 24条对焦线、中线
                       ELSE 48
                  END
             ELSE 0
        END AS m
       ,x,y,z
       ,POWER(2,ROWNUM-1) id
   FROM (SELECT LEVEL x FROM DUAL CONNECT BY LEVEL<=:N)
       ,(SELECT LEVEL y FROM DUAL CONNECT BY LEVEL<=:N)
       ,(SELECT LEVEL z FROM DUAL CONNECT BY LEVEL<=:N)
)
,cells AS (
SELECT c1.id
      ,SUM(c2.id) neighbours
      ,MAX(c1.m) m
  FROM c c1,c c2
WHERE (c1.x,c1.y,c1.z) IN ((c2.x+1,c2.y,c2.z),(c2.x-1,c2.y,c2.z),(c2.x,c2.y+1,c2.z),(c2.x,c2.y-1,c2.z),(c2.x,c2.y,c2.z+1),(c2.x,c2.y,c2.z-1))
GROUP BY c1.id
)
SELECT SUM(m*COUNT(*)) total_cnt
  FROM (SELECT CONNECT_BY_ROOT(m) m
         FROM cells
       WHERE LEVEL=:N*:N*:N
       START WITH m>0
       CONNECT BY NOCYCLE BITAND(PRIOR neighbours,id)>0
       )
GROUP BY m;

TOTAL_CNT
----------
   4960608

Elapsed: 00:26:10.58

newkid

20题：结果是MODEL最快。

WITH t(n,q,r,lvl) AS (
SELECT LEVEL
      ,TRUNC(TO_NUMBER(LEVEL||'123456789')/7)
      ,MOD(TO_NUMBER(LEVEL||'123456789'),7)
      ,1
  FROM DUAL
WHERE LEVEL>11 AND SUBSTR(LEVEL,1,1)>SUBSTR(LEVEL,2,1)
CONNECT BY LEVEL<=99
UNION ALL
SELECT n
      ,TRUNC(TO_NUMBER(r||'123456789')/7)
      ,MOD(TO_NUMBER(r||'123456789'),7)
      ,lvl+1
  FROM t
WHERE lvl<99
)
,t2(n,q,r,lvl) AS (
SELECT n
      ,TRUNC(TO_NUMBER(n||'123456789')/7)
      ,MOD(TO_NUMBER(n||'123456789'),7)
      ,1
  FROM (SELECT TO_NUMBER(SUBSTR(n,2,1)||SUBSTR(n,1,1)) n FROM t WHERE lvl=99 AND r=0)
UNION ALL
SELECT n
      ,TRUNC(TO_NUMBER(r||'123456789')/7)
      ,MOD(TO_NUMBER(r||'123456789'),7)
      ,lvl+1
  FROM t2
WHERE lvl<99
)
SELECT * FROM t2 WHERE lvl=99 AND r=0
;


         N          Q          R        LVL
---------- ---------- ---------- ----------
        29  160493827          0         99

Elapsed: 00:00:00.22


WITH t(n,q,r,lvl) AS (
SELECT LEVEL
      ,TRUNC(TO_NUMBER(LEVEL||'123456789')/7)
      ,MOD(TO_NUMBER(LEVEL||'123456789'),7)
      ,1
  FROM DUAL
WHERE LEVEL>11 AND MOD(LEVEL,11)<>0
CONNECT BY LEVEL<=99
UNION ALL
SELECT n
      ,TRUNC(TO_NUMBER(r||'123456789')/7)
      ,MOD(TO_NUMBER(r||'123456789'),7)
      ,lvl+1
  FROM t
WHERE lvl<99
)
,d AS (SELECT * FROM t WHERE lvl=99 AND r=0)
SELECT d1.n
  FROM d d1, d d2
WHERE d1.n<d2.n AND d1.n=SUBSTR(d2.n,2,1)||SUBSTR(d2.n,1,1)


         N
----------
        29

Elapsed: 00:00:00.54

WITH d AS (
SELECT *
  FROM(SELECT *
         FROM (SELECT LEVEL n
                     ,LEVEL r
                FROM DUAL
               WHERE LEVEL>11 AND MOD(LEVEL,11)<>0
              CONNECT BY LEVEL<=99
              )
       MODEL
       PARTITION BY (n)
       DIMENSION BY (0 lvl)
       MEASURES (0 q,r)
       RULES
       ITERATE (99)
         (
            q[ITERATION_NUMBER+1]=TRUNC(TO_NUMBER(r[ITERATION_NUMBER]||'123456789')/7),
            r[ITERATION_NUMBER+1]=MOD(TO_NUMBER(r[ITERATION_NUMBER]||'123456789'),7)
         )
      )
WHERE lvl=99 AND r=0
)
SELECT d1.n
  FROM d d1, d d2
WHERE d1.n<d2.n AND d1.n=SUBSTR(d2.n,2,1)||SUBSTR(d2.n,1,1)
;

         N
----------
        29

Elapsed: 00:00:00.07

如果最后不用输出商数，字段q的计算可以去掉。

newkid

在不需要商数，只保留余数的情况下，MODEL可以进一步改进，每个数只保留两个单元格辗转反复使用(通过对2取模实现)，这样临时内存占用就更少了，也减轻最后那个筛选的SQL的负担。

WITH d AS (
SELECT *
  FROM(SELECT *
         FROM (SELECT LEVEL n
                     ,LEVEL r
                FROM DUAL
               WHERE LEVEL>11 AND MOD(LEVEL,11)<>0
              CONNECT BY LEVEL<=99
              )
       MODEL
       PARTITION BY (n)
       DIMENSION BY (0 lvl)
       MEASURES (r)
       RULES
       ITERATE (99)
         (
            r[MOD(ITERATION_NUMBER+1,2)]=MOD(TO_NUMBER(r[MOD(ITERATION_NUMBER,2)]||'123456789'),7)
         )
      )
WHERE lvl=1 AND r=0
)
SELECT d1.n
  FROM d d1, d d2
WHERE d1.n<d2.n AND d1.n=SUBSTR(d2.n,2,1)||SUBSTR(d2.n,1,1)
;

         N
----------
        29

Elapsed: 00:00:00.04

还可以模仿第一种写法，先求X比Y大的，反过来再MODEL一次，减少除法的次数：

WITH d AS (
       SELECT *
         FROM (SELECT LEVEL n
                     ,LEVEL r
                FROM DUAL
               WHERE LEVEL>11 AND SUBSTR(LEVEL,1,1)>SUBSTR(LEVEL,2,1)
              CONNECT BY LEVEL<=99
              )
       MODEL
       PARTITION BY (n)
       DIMENSION BY (0 lvl)
       MEASURES (r)
       RULES
       ITERATE (99)
         (
            r[MOD(ITERATION_NUMBER+1,2)]=MOD(TO_NUMBER(r[MOD(ITERATION_NUMBER,2)]||'123456789'),7)
         )
)
SELECT n
  FROM(SELECT *
         FROM (SELECT TO_NUMBER(SUBSTR(n,2,1)||SUBSTR(n,1,1)) n
                     ,TO_NUMBER(SUBSTR(n,2,1)||SUBSTR(n,1,1)) r
                 FROM d
                WHERE lvl=1 AND r=0
              )
       MODEL
       PARTITION BY (n)
       DIMENSION BY (0 lvl)
       MEASURES (r)
       RULES
       ITERATE (99)
         (
            r[MOD(ITERATION_NUMBER+1,2)]=MOD(TO_NUMBER(r[MOD(ITERATION_NUMBER,2)]||'123456789'),7)
         )
      )
WHERE lvl=1 AND r=0
;

Elapsed: 00:00:00.04

newkid

其实轮流用两个格子的方法也可以输出商数：
WITH d AS (
SELECT *
   FROM(SELECT *
          FROM (SELECT LEVEL n
                      ,MOD(LEVEL,7) r
                      ,CAST(TRUNC(LEVEL/7) AS VARCHAR2(2000)) q
                 FROM DUAL
                WHERE LEVEL>11 AND MOD(LEVEL,11)<>0
               CONNECT BY LEVEL<=99
               )
        MODEL
        PARTITION BY (n)
        DIMENSION BY (0 lvl)
        MEASURES (r,q)
        RULES
        ITERATE (99)
          (  q[MOD(ITERATION_NUMBER+1,2)]=q[MOD(ITERATION_NUMBER,2)]||LPAD(TRUNC(TO_NUMBER(r[MOD(ITERATION_NUMBER,2)]||'123456789')/7),9,'0'),
             r[MOD(ITERATION_NUMBER+1,2)]=MOD(TO_NUMBER(r[MOD(ITERATION_NUMBER,2)]||'123456789'),7)
          )
       )
WHERE lvl=1 AND r=0
)
SELECT d1.n,d1.q,d2.n,d2.q
   FROM d d1, d d2
WHERE d1.n<d2.n AND d1.n=SUBSTR(d2.n,2,1)||SUBSTR(d2.n,1,1)
;

         
         N
----------
Q
------------------------------------------------------------------------------------------------------------------------------------------------------
         N
----------
Q
------------------------------------------------------------------------------------------------------------------------------------------------------
        29
416049382701763668416049382701763668416049382701763668416049382701763668416049382701763668416049382701763668416049382701763668416049382701763668416049
382701763668416049382701763668416049382701763668416049382701763668416049382701763668416049382701763668416049382701763668416049382701763668416049382701
763668416049382701763668416049382701763668416049382701763668416049382701763668416049382701763668416049382701763668416049382701763668416049382701763668
416049382701763668416049382701763668416049382701763668416049382701763668416049382701763668416049382701763668416049382701763668416049382701763668416049
382701763668416049382701763668416049382701763668416049382701763668416049382701763668416049382701763668416049382701763668416049382701763668416049382701
7636684160493827017636684160493827017636684160493827017636684160493827017636684160493827017636684160493827017636684160493827017636684160493827
        92
131604938270176366841604938270176366841604938270176366841604938270176366841604938270176366841604938270176366841604938270176366841604938270176366841604
938270176366841604938270176366841604938270176366841604938270176366841604938270176366841604938270176366841604938270176366841604938270176366841604938270
176366841604938270176366841604938270176366841604938270176366841604938270176366841604938270176366841604938270176366841604938270176366841604938270176366
841604938270176366841604938270176366841604938270176366841604938270176366841604938270176366841604938270176366841604938270176366841604938270176366841604
938270176366841604938270176366841604938270176366841604938270176366841604938270176366841604938270176366841604938270176366841604938270176366841604938270
17636684160493827017636684160493827017636684160493827017636684160493827017636684160493827017636684160493827017636684160493827017636684160493827


如果有兴趣可以再编个大数乘法验证一下。


select mod(123456789,7) from dual;

MOD(123456789,7)
----------------
               1

------- 把这余数1拼上去：
select mod(1123456789,7) from dual;

MOD(1123456789,7)
-----------------
                0

这就说明，只要把第一段解决了，使得 **123456789 能被7整除，后面拼上任意N次123456789，只要N为偶数，整个大数就可被7整除。

chicheng_cn421

感觉自己还差的好远呢。。。。

lastwinner

newkid 发表于 2011-12-8 00:42
20题就是大数除法，用递归WITH或MODEL都可以。

19题我想扩展到N*N*N的立方体，结果N=3就很难出来了：

20题不必这么麻烦，一个数（两位以上）能被7整除，假设这个数为ABCD...YZ，则一定有ABCD...Y-2*z的结果可以被7整除

再者，任意一个整数，若其是由一组数字连续出现6次而构成，则该数一定能被7整除
由于XY(123456789){99}可以被7整除，因此一定有XY(123456789){3}可以被7整除（这里用的正则表示法），因为(123456789){6}是一定可以被7整除的

所以问题就简化为
XY(123456789){3}按照一开始说的规则可以被7整除，循环计算：
先从第三个123456789开始算
12345678-9*2=12345660
123456-6*2=123444
12344-4*2=12336
1233-6*2=1221
122-1*2=120
接续第二个123456789：
1234567891-2*2=1234567887
123456788-7*2=123456774
12345677-4*2=12345669
1234566-9*2=1234548
123454-8*2=123438
12343-8*2=12327
1232-7*2=1218
121-8*2=105
10-5*2=0
这说明(123456789){2}可以被7整除
那问题就成了XY123456789以及YX123456789都能被7整除
借用刚才的结果，可得
XY12和YX12均能被7整除
mod(1000,7)=6, mod(100,7)=2 mod(10,7)=3，所以有
6X+2Y+3+2可以被7整除
6Y+2X+3+2可以被7整除

nnd，不自己算了，写sql去

lastwinner

with tmp as (select rownum rn from dual connect by rownum<=9)
select a.rn x, b.rn y from tmp a, tmp b where a.rn>b.rn and mod(6*a.rn+2*b.rn+5,7)=0 and  mod(2*a.rn+6*b.rn+5,7)=0
/

得X＝9，Y＝2

lastwinner

傻了，6X+2Y+3+2可以被7整除，6Y+2X+3+2可以被7整除
那么一定有(6X+2Y+3+2)-(6Y+2X+3+2)可以被7整除
于是有4(X-Y)可以被7整除，由于XY互换不影响结果，故而假定X>Y，而题设说XY是两位整数，因此X和Y均不可能是0
则有{X,Y}解集为[{8,1},{9,2}]
分别代入6X+2Y+3+2和6Y+2X+3+2，可得{8,1}不是所要的解，{9,2}才是