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

〇〇 · 发表于 2010-9-2 20:36

WITH p AS (
SELECT pos,l
FROM (SELECT ROWNUM pos FROM DUAL CONNECT BY ROWNUM<=10),(SELECT ROWNUM l FROM DUAL CONNECT BY ROWNUM<=3)
  )
,d3 as
(select rownum rn,num, numnum from
(select num, power(num,2) numnum from (select to_char(level+99,'fm999') num from dual connect by level<=999-100))
where length(numnum||num)=10-length(translate('0123456789','$'||numnum||num,'$')))
,t (str,len,path) AS (
/*SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') ,LEVEL,''
  FROM (SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
START WITH n>0
CONNECT BY NOCYCLE LEVEL<=3
*/
select a,length(a),'' from (select to_char(level,'fm999') a from dual connect by level<=999)
where a<=9
or(a>=10 and a<=99 and mod(a,11)>0)
or(a>=100 and (substr(a,1,1)<>substr(a,2,1) and substr(a,1,1)<>substr(a,3,1) and substr(a,3,1)<>substr(a,2,1)))
UNION ALL
SELECT SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+l)
   ,LENGTH(SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+l))
   ,path||SUBSTR(str,1,pos-1)||'('||SUBSTR(str,pos,l)||')'||SUBSTR(str,pos+l)||','
FROM t,p
  WHERE pos+l-1<=t.len  and substr(SUBSTR(str,pos,l),-1)<>'0' and SUBSTR(str,p.pos,p.l)>'1' and (l<3 or SUBSTR(str,pos,l)in( select num from d3))
      AND LENGTH(TRANSLATE('1234567890','$'||SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+l),'$'))
         = 10 - LENGTH(SUBSTR(str,1,pos-1)||TO_CHAR(SUBSTR(str,pos,l)*SUBSTR(str,pos,l))||SUBSTR(str,pos+l))
)
CYCLE str SET cycle_flag TO 'Y' DEFAULT 'N'
SELECT path||str FROM (
SELECT * FROM t ORDER BY len DESC,str DESC
)
WHERE ROWNUM=1;

xeon
PATH||STR
---------------------------------------------------------------------------------
38(7),38(49),(3)82401,98(24)01,98(5)7601,98(2)57601,98457(6)01,984573601

已用时间:  00: 00: 34.67

[ 本帖最后由〇〇于 2010-9-2 20:48 编辑 ]

〇〇 · 发表于 2010-9-2 20:50

79/81楼的算法错误，n 和n*n可以有重复数字...

haiersknl · 发表于 2010-9-2 21:16

版主，你的算法还是不对，你仔细看看

newkid · 发表于 2010-9-2 21:35

原帖由 haiersknl 于 2010-9-2 21:16 发表
版主，你的算法还是不对，你仔细看看

哪个版主？

newkid · 发表于 2010-9-2 21:47

如果把ROWNUM=1改为ROWNUM<=10, 可以看到其他路径，不过都是一样的，就是替换的先后顺序不同而已：
PATH||STR
-----------------------------------------------------------------------------------------------
38(7),38(49),(3)82401,98(24)01,98(5)7601,98(2)57601,98457(6)01,984573601
38(7),38(49),(3)82401,98(24)01,98(5)7601,98(2)57601,98457(6)01,9845736(0)1,984573601
38(7),38(49),38(24)01,38(5)7601,38(2)57601,(3)8457601,98457(6)01,984573601
38(7),38(49),38(24)01,38(5)7601,(3)8257601,98257(6)01,98(2)573601,984573601
38(7),38(49),38(24)01,38(5)7601,(3)8257601,98(2)57601,98457(6)01,984573601
38(7),38(49),38(24)01,(3)857601,9857(6)01,98(5)73601,98(2)573601,984573601
38(7),38(49),38(24)01,(3)857601,98(5)7601,98257(6)01,98(2)573601,984573601
38(7),38(49),38(24)01,(3)857601,98(5)7601,98(2)57601,98457(6)01,984573601
38(7),38(49),(3)82401,98(24)01,9857(6)01,98(5)73601,98(2)573601,984573601
38(7),38(49),(3)82401,98(24)01,98(5)7601,98257(6)01,98(2)573601,984573601

newkid · 发表于 2010-9-2 22:02

原帖由 haiersknl 于 2010-9-2 20:19 发表
7楼的答案17 不是最优的，请你重新审视你的程序。

可否贴出你的答案？（就是第二次入座后的顺序）
谢谢！

lastwinner · 发表于 2010-9-2 23:17

原帖由〇〇于 10-9-2 20:50 发表
79/81楼的算法错误，n 和n*n可以有重复数字...

╮(╯_╰)╭
你参照我78楼贴的不就好了么……

newkid · 发表于 2010-9-2 23:37

原帖由 lastwinner 于 2010-9-2 23:17 发表

╮(╯_╰)╭
你参照我78楼贴的不就好了么……

我把他的d3换成你的，确实效率高很多。
如果没有3位限制呢？也就是可以划掉任意连续位然后代之以平方。

newkid · 发表于 2010-9-2 23:42

去除3位限制：（相当于5位限制，因为最小的123456平方也超过10位了）
WITH p AS (
SELECT pos,l
FROM (SELECT ROWNUM pos FROM DUAL CONNECT BY ROWNUM<=10),(SELECT ROWNUM l FROM DUAL CONNECT BY ROWNUM<=5)
  WHERE pos+l<=11
  )
,t (str,len,path) AS (
SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') ,LEVEL,''
  FROM (SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
START WITH n>0
CONNECT BY NOCYCLE LEVEL<=3
UNION ALL
SELECT SUBSTR(str,1,p.pos-1)||TO_CHAR(SUBSTR(str,p.pos,p.l)*SUBSTR(str,p.pos,p.l))||SUBSTR(str,p.pos+p.l)
   ,LENGTH(SUBSTR(str,1,p.pos-1)||TO_CHAR(SUBSTR(str,p.pos,p.l)*SUBSTR(str,p.pos,p.l))||SUBSTR(str,p.pos+p.l))
   ,path||SUBSTR(str,1,p.pos-1)||'('||SUBSTR(str,p.pos,p.l)||')'||SUBSTR(str,p.pos+p.l)||','
FROM t,p
  WHERE p.pos+p.l-1<=t.len
      and substr(SUBSTR(str,pos,l),-1)<>'0' and SUBSTR(str,p.pos,p.l)>'1'
      AND LENGTH(TRANSLATE('1234567890','$'||SUBSTR(str,1,p.pos-1)||TO_CHAR(SUBSTR(str,p.pos,p.l)*SUBSTR(str,p.pos,p.l))||SUBSTR(str,p.pos+p.l),'$'))
         = 10 - LENGTH(SUBSTR(str,1,p.pos-1)||TO_CHAR(SUBSTR(str,p.pos,p.l)*SUBSTR(str,p.pos,p.l))||SUBSTR(str,p.pos+p.l))
)
CYCLE str SET cycle_flag TO 'Y' DEFAULT 'N'
SELECT path||str FROM (
SELECT * FROM t ORDER BY len DESC,str DESC
)
WHERE ROWNUM<=1;

PATH||STR
------------------------------------------------------
31(5),31(2)5,314(5),(3142)5,98721(6)45,987213645

Elapsed: 00:00:37.38

〇〇 · 发表于 2010-9-3 09:06

原帖由 lastwinner 于 2010-9-2 16:54 发表

赞

ps：三位数里有满足题设条件的

with p as (select rownum-1 rn from dual connect by rownum<=10),
three_digits as (select replace(sys_connect_by_path(rn,','),',','') num from p where level=3 start with rn>0 connect by nocycle rn<>prior rn and level<=3)
select num, numnum from
(select num, power(num,2) numnum from three_digits)
where length(numnum)=11-length(translate('0123456789',numnum,'$'))
/

硬是看不懂,你把平方数的第一位换成$为什么

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