PUZZLEUP 2014

〇〇

〇〇

newkid 发表于 2014-10-17 02:54
不用笛卡尔积，直接两个递归速度更快：

WITH s(n) AS (

你这个返回很多重复的行

〇〇

peter1166 发表于 2014-10-16 22:20
您这个是最快的，
如果我偷用你的递归， 速度跟这个差不多。

T1求所有子串的方法不错

newkid

〇〇 发表于 2014-10-17 22:20
你这个返回很多重复的行

什么重复行？只有一行。

SQL> VAR S VARCHAR2(30);
SQL> EXEC :S := '21218453415461109221';

PL/SQL procedure successfully completed.

Elapsed: 00:00:00.02
SQL> WITH s(n) AS (
  2  SELECT 1 FROM DUAL
  3  UNION ALL
  4  SELECT n*2 + 1 - MOD(n,2) FROM s WHERE n<TO_NUMBER(:s)
  5  )
  6  ,r(n,cnt,r) AS (
  7  SELECT TO_CHAR(n),1,TO_CHAR(n) FROM s WHERE :s LIKE n||'%'
  8  UNION ALL
  9  SELECT r.n||s.n,cnt+1,r||','||s.n FROM r,s WHERE :s LIKE r.n||s.n||'%'
10  )
11  SELECT r FROM r WHERE n=:s AND cnt=6;

R
---------------------------------------------------------------------------------
21,21845,341,5461,10922,1

Elapsed: 00:00:00.02

〇〇

newkid 发表于 2014-10-17 22:50
什么重复行？只有一行。

SQL> VAR S VARCHAR2(30);

难道是bug?
SQL>  var s varchar2(100)
SQL> exec :s:='75059993789508200000'
已用时间:  00: 00: 00.00
SQL> WITH s(n) AS (
  2  select level-1 c from dual connect by level<=2
  3  UNION ALL
  4  SELECT n*2 + 1 - MOD(n,2) FROM s WHERE n<TO_NUMBER(:s)
  5  )
  6  ,r(n,cnt,r) AS (
  7  SELECT TO_CHAR(n),1,TO_CHAR(n) FROM s WHERE :s LIKE n||'%'
  8  UNION ALL
  9  SELECT r.n||s.n,cnt+1,r||','||s.n FROM r,s WHERE :s LIKE r.n||s.n||'%'
10  )
11  SELECT r FROM r WHERE n=:s AND cnt=6;

R
--------------------------------------------------------------------------------------------------------------------------
750599937895082,0,0,0,0,0
750599937895082,0,0,0,0,0
已用时间:  00: 00: 00.01
SQL> exec :s:='21218453415461109221'
已用时间:  00: 00: 00.00
SQL> /

R
--------------------------------------------------------------------------------------------------------------------------
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
还有许多行
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
21,21845,341,5461,10922,1
已用时间:  00: 00: 00.12
SQL> show rel
release 1102000200

newkid

我是11.2.0.3，BUG少得多。

〇〇

newkid 发表于 2014-10-18 10:46
我是11.2.0.3，BUG少得多。

还不是，
我改了你的代码，没改前算不出带0的
SQL> /

R
--------------------------------------------------------------------------------------------------------------------------
21,21845,341,5461,10922,1
已用时间:  00: 00: 00.01
SQL> exec :s:='75059993789508200000'
已用时间:  00: 00: 00.00
SQL> /
已用时间:  00: 00: 00.01

〇〇

〇〇 发表于 2014-10-18 12:10
还不是，
我改了你的代码，没改前算不出带0的
SQL> /

把
SELECT 1 FROM DUAL
改成了
select level-1 c from dual connect by level<=2
但递归会层层叠加
应该把0放在最外面

〇〇

〇〇 发表于 2014-10-18 12:12
把
SELECT 1 FROM DUAL
改成了

这样就对了
SQL> WITH s(n) AS (
  2  SELECT 1 FROM DUAL
  3  UNION ALL
  4  SELECT n*2 + 1 - MOD(n,2) FROM s WHERE n<TO_NUMBER(:s)
  5  )
  6  ,s1 as (select * from s union all select 0 from dual)
  7  ,r(n,cnt,r) AS (
  8  SELECT TO_CHAR(n),1,TO_CHAR(n) FROM s1 s WHERE :s LIKE n||'%'
  9  UNION ALL
10  SELECT r.n||s.n,cnt+1,r||','||s.n FROM r,s1 s WHERE :s LIKE r.n||s.n||'%'
11  )
12  SELECT r FROM r WHERE n=:s AND cnt=6;

R
--------------------------------------------------------------------------------------------------------------------------
750599937895082,0,0,0,0,0
已用时间:  00: 00: 00.02

〇〇

No: 13       October 22, 2014
Points and Arrows


There are X points drawn on a paper. The points are connected by one-way arrows. All the points have exactly 4 arrows coming in, and exactly 4 arrows coming out.

If it is possible to reach to any point from any other point by following no more than two arrows, what can be the maximum value of X?


点和箭头


一张纸上有X个点。这些点由单向箭头连接。所有的点都恰好有4个箭头进来，正好4个箭头出来。

如果有可能通过不超过两个箭头来从任何其他点到达任何点，可能的X的最大值是多少？