Puzzleup 2013挑战赛即将开始

〇〇

〇〇 发表于 2013-8-15 09:11
四位相邻数字的和都是一个平方数
最多36
最小9

ft:1003都看不到

HelloWorld_001

newkid找到的81978100367936已经是符合条件最大的了
49#说的另外个数字是14位里面最长的了。剩下的就更小了

一个SQL能写出，但是效率太低了，拆成多个SQL了。

本来想构造20位的数字，发现实在构造不出来，太慢太慢了。
又想着用4位符合条件的数字拼出20位来

最终发现单个SQL效率太低，跑不出来结果。拆分成多个语句跑出来结果的

1. drop table test;
   
2. create table test as
   
3. with tm as (select lpad(level,4,'0') lv from dual connect by level<=9999)
   
4. select lv p from (select substr(lv,1,1) as  p1, substr(lv,2,1)as  p2, substr(lv,3,1)as  p3, substr(lv,4,1) as  p4,lv  from tm)
   
5. where p1+p2+p3+p4 in (1,4,9,16,25,36)
   
6. and REGEXP_COUNT(lv,0) in (0,1,2)
   
7. and REGEXP_COUNT(lv,1) in (0,1,2)
   
8. and REGEXP_COUNT(lv,2) in (0,1,2)
   
9. and REGEXP_COUNT(lv,3) in (0,1,2)
   
10. and REGEXP_COUNT(lv,4) in (0,1,2)
    
11. and REGEXP_COUNT(lv,5) in (0,1,2)
    
12. and REGEXP_COUNT(lv,6) in (0,1,2)
    
13. and REGEXP_COUNT(lv,7) in (0,1,2)
    
14. and REGEXP_COUNT(lv,8) in (0,1,2)
    
15. and REGEXP_COUNT(lv,9) in (0,1,2) ;
    
16. create unique index idx_test on test(p);
    
17. exec dbms_stats.gather_table_ststs(user,'test',cascade=>true);
    
18. 
    
19. drop table test2
    
20. create table test2 as
    
21. select num p from (select num
    
22. ,substr(num,2,4) as num11,substr(num,3,4) as num12,substr(num,4,4) as num13
    
23. from (select t1.p||t2.p as num
    
24. from test t1,test t2
    
25. where (t1.p<>t2.p))
    
26. where REGEXP_COUNT(num,0) in (0,1,2)
    
27. and REGEXP_COUNT(num,1) in (0,1,2)
    
28. and REGEXP_COUNT(num,2) in (0,1,2)
    
29. and REGEXP_COUNT(num,3) in (0,1,2)
    
30. and REGEXP_COUNT(num,4) in (0,1,2)
    
31. and REGEXP_COUNT(num,5) in (0,1,2)
    
32. and REGEXP_COUNT(num,6) in (0,1,2)
    
33. and REGEXP_COUNT(num,7) in (0,1,2)
    
34. and REGEXP_COUNT(num,8) in (0,1,2)
    
35. and REGEXP_COUNT(num,9) in (0,1,2)
    
36. ) a
    
37. where exists (select 1 from test where p=a.num11)
    
38. and exists (select 1 from test where p=a.num12)
    
39. and exists (select 1 from test where p=a.num13)
    
40. ;
    
41. 
    
42. --substr(num,1,14) 获取构造数字的前多少位，已经发现至少14才有符合条件的了
    
43. select num from (select substr(num,1,14) as num
    
44. ,substr(num,6,4) as num11,substr(num,7,4) as num12,substr(num,8,4) as num13
    
45. from (select t1.p||t2.p as num
    
46. from test2 t1,test2 t2
    
47. where (t1.p<>t2.p))
    
48. ) a
    
49. where exists (select 1 from test where p=a.num11)
    
50. and exists (select 1 from test where p=a.num12)
    
51. and exists (select 1 from test where p=a.num13)
    
52. and REGEXP_COUNT(num,0) in (0,1,2)
    
53. and REGEXP_COUNT(num,1) in (0,1,2)
    
54. and REGEXP_COUNT(num,2) in (0,1,2)
    
55. and REGEXP_COUNT(num,3) in (0,1,2)
    
56. and REGEXP_COUNT(num,4) in (0,1,2)
    
57. and REGEXP_COUNT(num,5) in (0,1,2)
    
58. and REGEXP_COUNT(num,6) in (0,1,2)
    
59. and REGEXP_COUNT(num,7) in (0,1,2)
    
60. and REGEXP_COUNT(num,8) in (0,1,2)
    
61. and REGEXP_COUNT(num,9) in (0,1,2)
    
62. ;
    
63. --63976300187918
    
64. --81978100367936

复制代码

--以下是单个SQL，希望大神给我优化下

1. with tm as (select lpad(level,4,'0') lv from dual connect by level<=9999)
   
2. ,test as (select lv p from (select substr(lv,1,1) as  p1, substr(lv,2,1)as  p2, substr(lv,3,1)as  p3, substr(lv,4,1) as  p4,lv  from tm)
   
3. where p1+p2+p3+p4 in (1,4,9,16,25,36)
   
4. and REGEXP_COUNT(lv,0) in (0,1,2)
   
5. and REGEXP_COUNT(lv,1) in (0,1,2)
   
6. and REGEXP_COUNT(lv,2) in (0,1,2)
   
7. and REGEXP_COUNT(lv,3) in (0,1,2)
   
8. and REGEXP_COUNT(lv,4) in (0,1,2)
   
9. and REGEXP_COUNT(lv,5) in (0,1,2)
   
10. and REGEXP_COUNT(lv,6) in (0,1,2)
    
11. and REGEXP_COUNT(lv,7) in (0,1,2)
    
12. and REGEXP_COUNT(lv,8) in (0,1,2)
    
13. and REGEXP_COUNT(lv,9) in (0,1,2))
    
14. ,test2 as (select num p from (select num
    
15. ,substr(num,2,4) as num11,substr(num,3,4) as num12,substr(num,4,4) as num13
    
16. from (select t1.p||t2.p as num
    
17. from test t1,test t2
    
18. where (t1.p<>t2.p))
    
19. where REGEXP_COUNT(num,0) in (0,1,2)
    
20. and REGEXP_COUNT(num,1) in (0,1,2)
    
21. and REGEXP_COUNT(num,2) in (0,1,2)
    
22. and REGEXP_COUNT(num,3) in (0,1,2)
    
23. and REGEXP_COUNT(num,4) in (0,1,2)
    
24. and REGEXP_COUNT(num,5) in (0,1,2)
    
25. and REGEXP_COUNT(num,6) in (0,1,2)
    
26. and REGEXP_COUNT(num,7) in (0,1,2)
    
27. and REGEXP_COUNT(num,8) in (0,1,2)
    
28. and REGEXP_COUNT(num,9) in (0,1,2)
    
29. ) a
    
30. where exists (select 1 from test where p=a.num11)
    
31. and exists (select 1 from test where p=a.num12)
    
32. and exists (select 1 from test where p=a.num13))
    
33. select num from (select substr(num,1,14) as num
    
34. ,substr(num,6,4) as num11,substr(num,7,4) as num12,substr(num,8,4) as num13
    
35. from (select t1.p||t2.p as num
    
36. from test2 t1,test2 t2
    
37. where (t1.p<>t2.p))
    
38. ) a
    
39. where exists (select 1 from test where p=a.num11)
    
40. and exists (select 1 from test where p=a.num12)
    
41. and exists (select 1 from test where p=a.num13)
    
42. and REGEXP_COUNT(num,0) in (0,1,2)
    
43. and REGEXP_COUNT(num,1) in (0,1,2)
    
44. and REGEXP_COUNT(num,2) in (0,1,2)
    
45. and REGEXP_COUNT(num,3) in (0,1,2)
    
46. and REGEXP_COUNT(num,4) in (0,1,2)
    
47. and REGEXP_COUNT(num,5) in (0,1,2)
    
48. and REGEXP_COUNT(num,6) in (0,1,2)
    
49. and REGEXP_COUNT(num,7) in (0,1,2)
    
50. and REGEXP_COUNT(num,8) in (0,1,2)
    
51. and REGEXP_COUNT(num,9) in (0,1,2)
    
52. ;

复制代码

HelloWorld_001

硬币那题试着用SQL写了下，效率太低
后来看了newkid用100-xx 代替最后的参数,而且把not in 改成minus瞬间出结果了。1明显不符合要求

1. with t1 as (select 1 as u1, 5 as u2, 10 as u3, 20 as u4, 25 as u5, 50 as u6, 100 as u7 from dual)
   
2. ,t as (select level-1 lv from dual connect by level<=102)
   
3. select level lv from dual connect by level<=101
   
4. minus
   
5. select distinct sumlv from (
   
6. select (100 - 5*c2.lv - 10*c3.lv - 20*c4.lv - 25*c5.lv - 50*c6.lv),c2.lv,c3.lv,c4.lv,c5.lv,c6.lv,(100 - 5*c2.lv - 10*c3.lv - 20*c4.lv - 25*c5.lv - 50*c6.lv) +c2.lv+c3.lv+c4.lv+c5.lv+c6.lv as sumlv
   
7. from t1,t c2,t c3,t c4,t c5,t c6
   
8. where  u2*c2.lv + u3*c3.lv + u4*c4.lv + u5*c5.lv + u6*c6.lv <=100
   
9. and c6.lv <=100/50
   
10. and c5.lv <=100/25
    
11. and c4.lv <=100/20
    
12. and c3.lv <=100/10
    
13. and c2.lv <=100/5
    
14. )
    
15. ;

复制代码

〇〇

HelloWorld_001 发表于 2013-8-16 14:41
newkid找到的81978100367936已经是符合条件最大的了
49#说的另外个数字是14位里面最长的了。剩下的就更小了 ...

我的也很慢
SQL> with s as (select '0123456789０１２３４５６７８９' d from dual),
  2  t as (select substr(d,level,1)c, TO_SINGLE_BYTE(substr(d,level,1))l from s connect by level<=length(d)),
  3  t2 as(
  4  select a.c||b.c||c.c||d.c c4 ,--字面
  5  a.l||b.l||c.l||d.l v4 --实际
  6  from t a,t b,t c,t d
  7  where a.l+b.l+c.l+d.l in(4,9,16,25)
  8  and a.l<>0),
  9  r(cx,vx,lv)as(
10  select cast(c4 as varchar(40)),cast(v4 as varchar(40)),1 from t2
11  union all
12  select cx||c,vx||TO_SINGLE_BYTE(c),lv+1 from r,t
13  where
14  instr(cx,c)=0 --判断出现2次，新字符不能出现在已有串中
15  and substr(vx,-1,1)+substr(vx,-2,1)+substr(vx,-3,1)+TO_SINGLE_BYTE(c) in(4,9,16,25)
16  and lv<=3)
17  select max(vx) from r where lv=4;

MAX(VX)
--------------------------------------------
9970907

已用时间:  00: 00: 04.33

〇〇

〇〇 发表于 2013-8-16 16:11
我的也很慢
SQL> with s as (select '0123456789０１２３４５６７８９' d from dual),
  2  t as (sele ...

优化了一些，但还是有错，答案有3个9
SQL> with s as (select '0123456789０１２３４５６７８９' d from dual),
  2  t as (select substr(d,level,1)c, TO_SINGLE_BYTE(substr(d,level,1))l from s connect by level<=length(d)),
  3  t2 as(
  4  select a.c||b.c||c.c||d.c c4 ,--字面
  5  a.l||b.l||c.l||d.l v4 --实际
  6  from t a,t b,t c,t d
  7  where a.l+b.l+c.l+d.l in(4,9,16,25)
  8  and a.l<>0
  9  and length(a.c||b.c||c.c||d.c)=lengthb(a.c||b.c||c.c||d.c)
10  ),
11  r(cx,vx,lv)as(
12  select cast(c4 as varchar(40)),cast(v4 as varchar(40)),1 from t2
13  union all
14  select cx||c,vx||TO_SINGLE_BYTE(c),lv+1 from r,t
15  where
16  instr(cx,c)=0 --判断出现2次，新字符不能出现在已有串中
17  and substr(vx,-1,1)+substr(vx,-2,1)+substr(vx,-3,1)+TO_SINGLE_BYTE(c) in(4,9,16,25)
18  and lv<=3)
19  select max(vx) from r where lv=4;

MAX(VX)
--------------------------------------------
9970907

已用时间:  00: 00: 00.42

〇〇

〇〇 发表于 2013-8-16 16:18
优化了一些，但还是有错，答案有3个9
SQL> with s as (select '0123456789０１２３４５６７８９' d from ...

利用instr的第4个参数，终于改对了
set num 20
SQL> with t as (select level-1 l from dual connect by level<=10),
  2  t2 as(
  3  select
  4  a.l||b.l||c.l||d.l v4 --实际
  5  from t a,t b,t c,t d
  6  where a.l+b.l+c.l+d.l in(4,9,16,25)
  7  and a.l<>0
  8  ),
  9  r(vx,lv)as(
10  select cast(v4 as varchar(40)),1 from t2
11  union all
12  select vx||l,lv+1 from r,t
13  where
14  instr(vx,l,1,2)=0 --判断出现2次，新字符不能出现在已有串中
15  and substr(vx,-1,1)+substr(vx,-2,1)+substr(vx,-3,1)+l in(4,9,16,25)
16  and lv<=16)
17  select max(0+vx) from r;

           MAX(0+VX)
--------------------
      81978100367936

已用时间:  00: 00: 00.24

HelloWorld_001

我是单个SQL没执行除结果，你的执行很快很快了

〇〇

HelloWorld_001 发表于 2013-8-16 16:49
我是单个SQL没执行除结果，你的执行很快很快了

更精简的结果是更慢
set timi on
set num 20
with t as (select level-1 l from dual connect by level<=10),
r(v,lv)as(
select cast(l as varchar(40)),1 from t
union all
select v||l,lv+1 from r,t
where
instr(v,l,1,2)=0 --判断出现2次，新字符不能出现在已有串中
and (lv<3 or substr(v,-1,1)+substr(v,-2,1)+substr(v,-3,1)+l in(4,9,16,25))
and lv<=19)
select max(0+v) from r;

        MAX(0+V)
----------------
  81978100367936

时间:  00: 00: 00.76

〇〇

〇〇 发表于 2013-8-16 18:23
更精简的结果是更慢
set timi on
set num 20

看autotrace
精简的成本更低，但物理和逻辑读都比前一个高很多
统计信息
----------------------------------------------------------
          3  recursive calls
       7770  db block gets
      30827  consistent gets
vs
统计信息
----------------------------------------------------------
         10  recursive calls
       4292  db block gets
      26362  consistent gets

newkid

lugionline 发表于 2013-8-16 06:55
有两个吧
x
-------------------

你写的代码呢？
题目要求找最大。