Puzzleup 2010 比赛快开始了，大家用SQL解答啊

haiersknl

For the ninth one, my immediate answer is 206640, just by roughly selection.
I am not sure it is the optimum one before resorting to a program.

What is your answer? try it you Oracle geeks!

newkid

#9:

Multiplication

You will carry out a multiplication that will implement the steps below:

• Place 9 of the 10 digits (0-9) on a 3×3 grid on the condition that vertically or horizontally neighboring cells do not contain consecutive digits.
• Delete the largest digit in every row.
• Multiply the remaining two-digit numbers formed (from left to right) in every row.

What is the largest product that can be generated through this multiplication?

Example:


160
729
384


If the numbers were placed as above, than the multiplication yields 24480 (10×72×34).

newkid

穷尽法：

WITH t (d1,d2,d3,d4,d5,d6,d7,d8,d9,path,lvl) AS (
   SELECT LEVEL-1
         ,-1,-1,-1,-1,-1,-1,-1,-1
         ,TO_CHAR(LEVEL-1),1
     FROM DUAL CONNECT BY LEVEL<=10
   UNION ALL
   SELECT d1
         ,DECODE(lvl,1,n2,d2)
         ,DECODE(lvl,2,n2,d3)
         ,DECODE(lvl,3,n2,d4)
         ,DECODE(lvl,4,n2,d5)
         ,DECODE(lvl,5,n2,d6)
         ,DECODE(lvl,6,n2,d7)
         ,DECODE(lvl,7,n2,d8)
         ,DECODE(lvl,8,n2,d9)
         ,path||n2
         ,lvl+1
     FROM t,(SELECT LEVEL-1 n2 FROM DUAL CONNECT BY LEVEL<=10)
    WHERE INSTR(path,n2)=0
          AND (lvl NOT IN (3,6) AND SUBSTR(path,lvl,1) NOT IN (n2+1,n2-1)
               OR lvl IN (3,6)
              )
          AND (lvl>2 AND SUBSTR(path,lvl-2,1) NOT IN (n2+1,n2-1)
               OR lvl IN (1,2)
               )
)
,t2 AS (SELECT path,REPLACE(d1||d2||d3,GREATEST(d1,d2,d3))*REPLACE(d4||d5||d6,GREATEST(d4,d5,d6))*REPLACE(d7||d8||d9,GREATEST(d7,d8,d9)) m FROM t WHERE lvl=9)
SELECT * FROM (SELECT * FROM t2 ORDER BY m DESC) WHERE ROWNUM=1;


PATH               M
----------------- ---------
425809637         211680

Elapsed: 00:00:15.60

lastwinner

人肉出来一个
637
809
425

211680

〇〇

consecutive?

lastwinner

a>b, c>d ,ac表示a*10+c

ac*bd=100*a*b+10*(c*b+a*d)+c*d
ad*bc=100*a*b+10*(c*a+b*d)+c*d

ac*bd-ad*bc=10*((c*b+a*d)-(c*a+b*d))
因为(c*b+a*d)-(c*a+b*d)=c*(b-a)+d*(a-b)=(c-d)*(b-a)<0
所以ac*bd<ad*bc

所以在构造的时候，当个位数上有多个候选数时，较大的个位数应搭配十位数较小的那个，方能获得最大的乘积

newkid

原帖由 〇〇 于 2010-9-8 22:04 发表
consecutive?

就是上下左右相邻的数不能连续。
花花的肉很强......

lastwinner

你穷举只要算法没错，是可以证明得到的结果就是最大的
而我暂时没法证明这就是最大的，除非列举出所有满足构造的结果较大的组合，由结果证明当前的就是最大的
因为仅仅将当前的组合中任意一个数字替换为未使用的数字并无法证明这就是最大的

newkid

最原始的办法效率最高！

WITH
n AS (SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
SELECT * FROM (
SELECT n1.n||n2.n||n3.n||n4.n||n5.n||n6.n||n7.n||n8.n||n9.n path
      ,REPLACE(n1.n||n2.n||n3.n,GREATEST(n1.n,n2.n,n3.n))
       *REPLACE(n4.n||n5.n||n6.n,GREATEST(n4.n,n5.n,n6.n))
       *REPLACE(n7.n||n8.n||n9.n,GREATEST(n7.n,n8.n,n9.n)) m
  FROM n n1,n n2,n n3,n n4,n n5,n n6,n n7,n n8,n n9
WHERE n1.n NOT IN (n2.n,n3.n,n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
       AND n2.n NOT IN (n3.n,n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
       AND n3.n NOT IN (n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
       AND n4.n NOT IN (n5.n,n6.n,n7.n,n8.n,n9.n)
       AND n5.n NOT IN (n6.n,n7.n,n8.n,n9.n)
       AND n6.n NOT IN (n7.n,n8.n,n9.n)
       AND n7.n NOT IN (n8.n,n9.n)
       AND n8.n<>n9.n
       AND n1.n NOT IN (n2.n+1,n2.n-1) AND n2.n NOT IN (n3.n+1,n3.n-1)
       AND n4.n NOT IN (n5.n+1,n5.n-1) AND n5.n NOT IN (n6.n+1,n6.n-1)
       AND n7.n NOT IN (n8.n+1,n8.n-1) AND n8.n NOT IN (n9.n+1,n9.n-1)
       AND n1.n NOT IN (n4.n+1,n4.n-1) AND n4.n NOT IN (n7.n+1,n7.n-1)
       AND n2.n NOT IN (n5.n+1,n5.n-1) AND n5.n NOT IN (n8.n+1,n8.n-1)
       AND n3.n NOT IN (n6.n+1,n6.n-1) AND n6.n NOT IN (n9.n+1,n9.n-1)
ORDER BY 2 DESC
)
WHERE ROWNUM=1;

PATH         M
----------   ------
637809425    211680

Elapsed: 00:00:03.17

〇〇

原帖由 lastwinner 于 2010-9-8 22:11 发表
a>b, c>d ,ac表示a*10+c

ac*bd=100*a*b+10*(c*b+a*d)+c*d
ad*bc=100*a*b+10*(c*a+b*d)+c*d

ac*bd-ad*bc=10*((c*b+a*d)-(c*a+b*d))
因为(c*b+a*d)-(c*a+b*d)=c*(b-a)+d*(a-b)=(c-d)*(b-a)

越接近正方形，面积越大