puzzleup2012谜题，请用SQL或PLSQL解答

newkid

很不雅的暴力法，只能算到N=5, 看看能否找出规律再推广：

VAR N NUMBER;
EXEC :N:=4;

WITH g AS (
SELECT LEVEL-1 n
      ,TRUNC((LEVEL-1)/:N) r
      ,MOD(LEVEL-1,:N) c
      ,POWER(2,LEVEL-1) bit
  FROM DUAL CONNECT BY LEVEL<=:N*:N
)
,t(lvl,bits,path,diag,diag2,r,c)  AS (
SELECT 1,g.bit,CAST(r||'-'||c AS VARCHAR2(1000)),CASE WHEN r=c THEN 1 ELSE 0 END,CASE WHEN r+c=:N-1 THEN 1 ELSE 0 END,r,c
  FROM g
WHERE r<=TRUNC((:N-1)/2) AND c<=TRUNC((:N-1)/2)
       AND c>=r
UNION ALL
SELECT t.lvl+1
      ,t.bits+g.bit
      ,t.path||','||g.r||'-'||g.c
      ,t.diag + CASE WHEN g.r=g.c THEN lvl+1 ELSE 0 END
      ,t.diag2 + CASE WHEN g.r+g.c=:N-1 THEN lvl+1 ELSE 0 END
      ,g.r,g.c
  FROM t,g
WHERE BITAND(t.bits,g.bit)=0
       AND (t.r,t.c) IN ((g.r+1,g.c),(g.r-1,g.c),(g.r,g.c+1),(g.r,g.c-1))
)
SELECT GREATEST(diag,diag2),path FROM (
SELECT * FROM t WHERE lvl=:N*:N ORDER BY GREATEST(diag,diag2) DESC
)
WHERE ROWNUM=1
;


GREATEST(DIAG,DIAG2)
--------------------
PATH
---------------------------------------------------------------------
                  48
0-0,0-1,1-1,1-0,2-0,3-0,3-1,3-2,3-3,2-3,1-3,0-3,0-2,1-2,2-2,2-1


Elapsed: 00:00:00.13


SQL> EXEC :N:=5;

PL/SQL procedure successfully completed.

Elapsed: 00:00:00.00
SQL> /

GREATEST(DIAG,DIAG2)
--------------------
PATH
-----------------------------------------------------------------------------------------------------------
                  97
0-0,0-1,0-2,1-2,1-1,1-0,2-0,3-0,4-0,4-1,4-2,3-2,3-3,4-3,4-4,3-4,2-4,1-4,0-4,0-3,1-3,2-3,2-2,2-1,3-1


Elapsed: 00:00:49.17

〇〇

newkid 发表于 2012-8-1 23:11
#2 Diagonal Sum

Place the numbers 1 through 100 on a 10x10 square table so that all consecutive n ...

812
793
654这种放法合规？

newkid

〇〇 发表于 2012-8-2 06:50
812
793
654这种放法合规？

不行，不能走对角。
我观察的公式 SELECT POWER(:N,3)-:N*:N*2+3*:N-2 + (:N-2)*3 FROM DUAL;
就是说从N^2开始，连续N-1个最大数(递减2因为不能走对角)可以放在对角线上，剩下一个是 (N-2)*3
适用于3,4,5, 但是6无法验证。

〇〇

newkid 发表于 2012-8-2 00:17
很不雅的暴力法，只能算到N=5, 看看能否找出规律再推广：

VAR N NUMBER;

看了下路径好像是贴边走争取把最大的放偏右上角

〇〇

newkid 发表于 2012-8-2 08:01
不行，不能走对角。
我观察的公式 SELECT POWER(:N,3)-:N*:N*2+3*:N-2 + (:N-2)*3 FROM DUAL;
就是说从 ...

2*2：2，4
3*3：{3},7,9
4*4：12，14，16，{6}
5*5：19，21，23，25，{9}

〇〇

〇〇 发表于 2012-8-2 10:55
2*2：2，4
3*3：{3},7,9
4*4：12，14，16，{6}

6*6

〇〇

newkid 发表于 2012-8-2 08:01
不行，不能走对角。
我观察的公式 SELECT POWER(:N,3)-:N*:N*2+3*:N-2 + (:N-2)*3 FROM DUAL;
就是说从 ...

6也可以最后n-1个最大值，但多余的比(n-2)*3大

udfrog

newkid 发表于 2012-8-1 23:11
#2 Diagonal Sum

Place the numbers 1 through 100 on a 10x10 square table so that all consecutive n ...

1. with t as (
   
2. select        c, r
   
3. from        (select rownum c from dual connect by rownum<=10),
   
4.         (select rownum r from dual connect by rownum<=10)
   
5. ),
   
6. tmp as (
   
7. select        level lv, sys_connect_by_path(decode(c, 11-r, level, 0), '+') rst
   
8. from        t
   
9. start with greatest(c, r)<=5
   
10. connect by nocycle (prior c=c and (prior r=r+1 or prior r+1=r)) or (prior r=r and (prior c=c+1 or prior c+1=c)))
    
11. select        max(dbms_aw.eval_number('0'||rst))
    
12. from tmp
    
13. where        lv=100
    
14. /
    

复制代码

〇〇

udfrog 发表于 2012-8-2 11:46

出不来啊

with t as (
*
第 1 行出现错误:
ORA-01013: 用户请求取消当前的操作


已用时间:  00: 06: 03.98

ryax

870