PUZZLEUP 2014

lastwinner · 发表于 2014-8-27 10:59

newkid 发表于 2014-8-26 23:16
他用了NOCYCLE, 所以LEVEL不可能超过256了。
最后的WHERE LEVEL=POWER(4,4) 是属于“大胆假设小心求证” ...

对，nocycle确定了最多只能有256级level
但这同样隐含了256个字符串肯定能不重复的首尾串在一起这一假定，最终形成一个259字节字符串

这里似乎可以证明，无论字符串是多少字节，只要不重复字符的数量和字节数相等，假设为N，那么一定存在一个长度为N^N+N-1的字符串，可以将这N^N个字符串首尾相连的字符串包含在其中

lastwinner · 发表于 2014-8-27 11:15

newkid 发表于 2014-8-26 23:16
他用了NOCYCLE, 所以LEVEL不可能超过256了。
最后的WHERE LEVEL=POWER(4,4) 是属于“大胆假设小心求证” ...

“从AAAA出发也是一个大胆假设，并不等价于ABCD。如果是一个首尾衔接的环，那么从哪个出发就是等价的。”

其实既然可以从AAAA开始，那么从ABCD开始也是可以的，因为可选的路径不只是代码输出的这一条，所以不要因此产生“不是一个首尾衔接的环”的错觉

而且事实上，代码输出的，是一个闭环，如果楼上的推理（你也是这样推理的）成立，那么应该可以推出，这个一定是首尾相连的环

SCOTT@lw> WITH T1 AS ( select chr(64+rownum) a from dual connect by rownum<5)
  2  , T as (select a.a||b.a||c.a||d.a s from t1 a, t1 b, t1 c , t1 d)
  3  SELECT STR
  4  FROM (
  5    SELECT SYS_CONNECT_BY_PATH(S,'|') STR
  6    FROM T
  7    WHERE LEVEL = (SELECT COUNT(*) FROM T)
  8    CONNECT BY NOCYCLE PRIOR SUBSTR(S,2) =  SUBSTR(S,1,LENGTH(S)-1) AND PRIOR S <> S
  9    START WITH S IN ('ABCD')
10    )
11  WHERE ROWNUM=1
12  /

STR
--------------------------------------------------------------------------------
|ABCD|BCDA|CDAA|DAAA|AAAA|AAAB|AABA|ABAA|BAAA|AAAC|AACA|ACAA|CAAA|AAAD|AADA|ADAA
|DAAB|AABB|ABBA|BBAA|BAAB|AABC|ABCA|BCAA|CAAB|AABD|ABDA|BDAA|DAAC|AACB|ACBA|CBAA
|BAAC|AACC|ACCA|CCAA|CAAC|AACD|ACDA|CDAB|DABA|ABAB|BABA|ABAC|BACA|ACAB|CABA|ABAD
|BADA|ADAB|DABB|ABBB|BBBA|BBAB|BABB|ABBC|BBCA|BCAB|CABB|ABBD|BBDA|BDAB|DABC|ABCB
|BCBA|CBAB|BABC|ABCC|BCCA|CCAB|CABD|ABDB|BDBA|DBAA|BAAD|AADB|ADBA|DBAB|BABD|ABDC
|BDCA|DCAA|CAAD|AADC|ADCA|DCAC|CACA|ACAC|CACB|ACBB|CBBA|BBAC|BACB|ACBC|CBCA|BCAC
|CACC|ACCB|CCBA|CBAC|BACC|ACCC|CCCA|CCAC|CACD|ACDB|CDBA|DBAC|BACD|ACDC|CDCA|DCAD
|CADA|ADAC|DACA|ACAD|CADB|ADBB|DBBA|BBAD|BADB|ADBC|DBCA|BCAD|CADC|ADCB|DCBA|CBAD
|BADC|ADCC|DCCA|CCAD|CADD|ADDA|DDAA|DAAD|AADD|ADDB|DDBA|DBAD|BADD|ADDC|DDCB|DCBB
|CBBB|BBBB|BBBC|BBCB|BCBB|CBBC|BBCC|BCCB|CCBB|CBBD|BBDB|BDBB|DBBB|BBBD|BBDC|BDCB
|DCBC|CBCB|BCBC|CBCC|BCCC|CCCB|CCBC|CBCD|BCDB|CDBB|DBBC|BBCD|BCDC|CDCB|DCBD|CBDA
|BDAC|DACB|ACBD|CBDB|BDBC|DBCB|BCBD|CBDC|BDCC|DCCB|CCBD|CBDD|BDDA|DDAB|DABD|ABDD
|BDDB|DDBB|DBBD|BBDD|BDDC|DDCC|DCCC|CCCC|CCCD|CCDA|CDAC|DACC|ACCD|CCDB|CDBC|DBCC
|BCCD|CCDC|CDCC|DCCD|CCDD|CDDA|DDAC|DACD|ACDD|CDDB|DDBC|DBCD|BCDD|CDDC|DDCD|DCDA
|CDAD|DADA|ADAD|DADB|ADBD|DBDA|BDAD|DADC|ADCD|DCDB|CDBD|DBDB|BDBD|DBDC|BDCD|DCDC
|CDCD|DCDD|CDDD|DDDA|DDAD|DADD|ADDD|DDDB|DDBD|DBDD|BDDD|DDDD|DDDC|DDCA|DCAB|CABC

已用时间:  00: 00: 00.05
SCOTT@lw> WITH T1 AS ( select chr(64+rownum) a from dual connect by rownum<5)
  2  , T as (select a.a||b.a||c.a||d.a s from t1 a, t1 b, t1 c , t1 d)
  3  SELECT STR
  4  FROM (
  5    SELECT SYS_CONNECT_BY_PATH(S,'|') STR
  6    FROM T
  7    WHERE LEVEL = (SELECT COUNT(*) FROM T)
  8    CONNECT BY NOCYCLE PRIOR SUBSTR(S,2) =  SUBSTR(S,1,LENGTH(S)-1) AND PRIOR S <> S
  9    START WITH S IN ('AAAA')
10    )
11  WHERE ROWNUM=1
12  /

STR
--------------------------------------------------------------------------------
|AAAA|AAAB|AABA|ABAA|BAAA|AAAC|AACA|ACAA|CAAA|AAAD|AADA|ADAA|DAAB|AABB|ABBA|BBAA
|BAAB|AABC|ABCA|BCAA|CAAB|AABD|ABDA|BDAA|DAAC|AACB|ACBA|CBAA|BAAC|AACC|ACCA|CCAA
|CAAC|AACD|ACDA|CDAA|DAAD|AADB|ADBA|DBAA|BAAD|AADC|ADCA|DCAA|CAAD|AADD|ADDA|DDAB
|DABA|ABAB|BABA|ABAC|BACA|ACAB|CABA|ABAD|BADA|ADAB|DABB|ABBB|BBBA|BBAB|BABB|ABBC
|BBCA|BCAB|CABB|ABBD|BBDA|BDAB|DABC|ABCB|BCBA|CBAB|BABC|ABCC|BCCA|CCAB|CABC|ABCD
|BCDA|CDAB|DABD|ABDB|BDBA|DBAB|BABD|ABDC|BDCA|DCAB|CABD|ABDD|BDDA|DDAC|DACA|ACAC
|CACA|ACAD|CADA|ADAC|DACB|ACBB|CBBA|BBAC|BACB|ACBC|CBCA|BCAC|CACB|ACBD|CBDA|BDAC
|DACC|ACCB|CCBA|CBAC|BACC|ACCC|CCCA|CCAC|CACC|ACCD|CCDA|CDAC|DACD|ACDB|CDBA|DBAC
|BACD|ACDC|CDCA|DCAC|CACD|ACDD|CDDA|DDAD|DADA|ADAD|DADB|ADBB|DBBA|BBAD|BADB|ADBC
|DBCA|BCAD|CADB|ADBD|DBDA|BDAD|DADC|ADCB|DCBA|CBAD|BADC|ADCC|DCCA|CCAD|CADC|ADCD
|DCDA|CDAD|DADD|ADDB|DDBA|DBAD|BADD|ADDC|DDCA|DCAD|CADD|ADDD|DDDB|DDBB|DBBB|BBBB
|BBBC|BBCB|BCBB|CBBB|BBBD|BBDB|BDBB|DBBC|BBCC|BCCB|CCBB|CBBC|BBCD|BCDB|CDBB|DBBD
|BBDC|BDCB|DCBB|CBBD|BBDD|BDDB|DDBC|DBCB|BCBC|CBCB|BCBD|CBDB|BDBC|DBCC|BCCC|CCCB
|CCBC|CBCC|BCCD|CCDB|CDBC|DBCD|BCDC|CDCB|DCBC|CBCD|BCDD|CDDB|DDBD|DBDB|BDBD|DBDC
|BDCC|DCCB|CCBD|CBDC|BDCD|DCDB|CDBD|DBDD|BDDC|DDCB|DCBD|CBDD|BDDD|DDDC|DDCC|DCCC
|CCCC|CCCD|CCDC|CDCC|DCCD|CCDD|CDDC|DDCD|DCDC|CDCD|DCDD|CDDD|DDDD|DDDA|DDAA|DAAA

已用时间:  00: 00: 00.04

lastwinner · 发表于 2014-8-27 11:16

lastwinner 发表于 2014-8-27 11:15
“从AAAA出发也是一个大胆假设，并不等价于ABCD。如果是一个首尾衔接的环，那么从哪个出发就是等价的。” ...

试着拿3字节的做个反例，结果证实了上述猜测，也就是如果有结果，那结果一定是首尾衔接的闭环

SCOTT@lw> WITH T1 AS ( select chr(64+rownum) a from dual connect by rownum<4)
  2  , T as (select a.a||b.a||c.a s from t1 a, t1 b, t1 c )
  3  SELECT STR
  4  FROM (
  5    SELECT SYS_CONNECT_BY_PATH(S,'|') STR
  6    FROM T
  7    WHERE LEVEL = (SELECT COUNT(*) FROM T)
  8    CONNECT BY NOCYCLE PRIOR SUBSTR(S,2) =  SUBSTR(S,1,LENGTH(S)-1) AND PRIOR S <> S and (level<(SELECT COUNT(*) F
ROM T) or level=(SELECT COUNT(*) FROM T) and S like '_AB')
  9    START WITH S IN ('AAA')
10    )
11  WHERE ROWNUM<=1
12  /

未选定行

已用时间:  00: 01: 02.13
SCOTT@lw> WITH T1 AS ( select chr(64+rownum) a from dual connect by rownum<4)
  2  , T as (select a.a||b.a||c.a s from t1 a, t1 b, t1 c )
  3  SELECT STR
  4  FROM (
  5    SELECT SYS_CONNECT_BY_PATH(S,'|') STR
  6    FROM T
  7    WHERE LEVEL = (SELECT COUNT(*) FROM T)
  8    CONNECT BY NOCYCLE PRIOR SUBSTR(S,2) =  SUBSTR(S,1,LENGTH(S)-1) AND PRIOR S <> S and (level<(SELECT COUNT(*) F
ROM T) or level=(SELECT COUNT(*) FROM T) and S not like '_AA')
  9    START WITH S IN ('AAA')
10    )
11  WHERE ROWNUM<=1
12  /

未选定行

已用时间:  00: 01: 03.90

lastwinner · 发表于 2014-8-27 11:18

newkid 发表于 2014-8-21 21:25
陆虎转给你了！
我从没考虑过CONNECT BY，谁知道它这么给力？由此可推测内部是深度优先的。

实际用的时候发现，stopkey比较给力，找到一个就直接返回结果，其他的就不去算了

udfrog · 发表于 2014-8-27 18:54

第三题的数学解法应该是这样的
(C(10, 3)*3*2*C(7, 3)*6)*(C(10, 3)*C(7, 1)*C(6, 2))*(9/10)
=()*()*9/10
=(3个1次的位置组合*3个3次的位置组合*2个2次的位置组合)*(1次的数字选择*3次的数字选择*2次的数字选择)*0在首位占90%

newkid · 发表于 2014-8-27 23:04

udfrog 发表于 2014-8-27 18:54
第三题的数学解法应该是这样的
(C(10, 3)*3*2*C(7, 3)*6)*(C(10, 3)*C(7, 1)*C(6, 2))*(9/10)
=()*()*9/1 ...

你最后这个9/10果然是神来之笔，让公式简化了很多！

newkid · 发表于 2014-8-27 23:04

#5 Neighboring Digits

What is the greatest number in which all the digits, except the first and the last digit, are smaller than the geometric mean of its neighbors? (Neighbors of a digit are the digits to the immediate left and right of that digit)

相邻的数字
在一个数中，除了第一位和最后一位，每一位都比其相邻数的几何平均数小，这样的数最大是多少？相邻的数指的是这位数紧挨着的左边或者右边的一位。

两个数的几何平均数即它们乘积的平方根。

虽然这道题很简单，第一个写出来的还是有章。

peter1166 · 发表于 2014-8-28 09:25

95322359 对么？

peter1166 · 发表于 2014-8-28 09:29

WITH T AS (SELECT LEVEL N FROM DUAL CONNECT BY LEVEL < 10)
   ,T1 AS (
         SELECT A,C,B ,LEVEL L
         FROM (
            SELECT T1.N A, T2.N B
                     ,CASE WHEN FLOOR(SQRT(T1.N * T2.N)) = SQRT(T1.N * T2.N) THEN SQRT(T1.N * T2.N) -1 ELSE FLOOR(SQRT(T1.N * T2.N)) END C
            FROM T T1, T T2
            WHERE T1.N < T2.N
            )
         CONNECT BY PRIOR A = A AND PRIOR B = B AND LEVEL <= C AND PRIOR DBMS_RANDOM.VALUE IS NOT NULL
         )
SELECT MAX(N)
FROM (
   SELECT A,L,B,S , SYS_CONNECT_BY_PATH(S,'|') , TO_NUMBER(SUBSTR(CONNECT_BY_ROOT(S),1,2)||REPLACE(SYS_CONNECT_BY_PATH(SUBSTR(S,3),'|'),'|')) N
   FROM (
         SELECT T1.A , T1.L , T1.B, T1.A||T1.L||T1.B S FROM T1
         UNION ALL
         SELECT T1.B,  T1.L , T1.A, T1.B||T1.L||T1.A S FROM T1
         )
   WHERE  CONNECT_BY_ISLEAF = 1
   CONNECT BY PRIOR SUBSTR(S,2) = SUBSTR(S,1,2)
   )
/
MAX(N)
----------
  95322359

-- 验证用 SQL 。
WITH T AS (SELECT '95322359' N FROM DUAL)
SELECT T1.*
   ,CASE WHEN T1.C1< SQRT(T1.C2 * T1.C3) THEN 'Y' ELSE 'N' END CHK_YN
FROM (
   SELECT N ,LEVEL L
         ,SUBSTR(N,LEVEL,1) C1
         ,SUBSTR(N,LEVEL+1,1) C2
         ,SUBSTR(N,LEVEL-1,1) C3
   FROM T
   CONNECT BY LEVEL <= (SELECT LENGTH(N) FROM T)
   ) T1
/
N                L C1 C2 C3 CHK_YN
-------- ---------- ---- ---- ---- ------
95322359       1 9 5 9 N
95322359       2 5 3 9 Y
95322359       3 3 2 5 Y
95322359       4 2 2 3 Y
95322359       5 2 3 2 Y
95322359       6 3 5 2 Y
95322359       7 5 9 3 Y
95322359       8 9       5 N

solomon_007 · 发表于 2014-8-28 11:29

peter1166 发表于 2014-8-28 09:29
WITH T AS (SELECT LEVEL N FROM DUAL CONNECT BY LEVEL < 10)
,T1 AS (
SELECT A, ...

这种首尾拼接的方法很有效啊，跟上一题有点像！

PUZZLEUP 2014

浏览过的版块