puzzleup 2011

newkid · 发表于 2011-9-15 22:09

S=(c11+c12+c21+c22)+(c12+c13+c22+c23)+(c13+c14+c23+c24)
+(c21+c22+c31+c32)+(c22+c23+c32+c33)+(c23+c24+c33+c34)
+(c31+c32+c41+c42)+(c32+c33+c42+c43)+(c33+c34+c43+c44)
对换位置：
(c11+c12+c13+c14)+(c21+c22+c23+c24)
+(c31+c32+c33+c34)+(c41+c42+c43+c44)
+(c12+c22+c32+c42)
+(c13+c23+c33+c43)
+(c21+c22+c23+c24)+(c31+c32+c33+c34)
+(c22+c23+c32+c33)

除了最后四个，其他的和都是34。
最后四个是中间的四个数，加上四个角就等于两条对角线：

(c22+c23+c32+c33)+C11+C14+C41+C44 = 68

这两条对角线之和也等于第一+第四行之和：
(c12+c13+c42+c43)+C11+C14+C41+C44 = 68

得到(c22+c23+c32+c33)=(c12+c13+c42+c43)
而(c22+c23+c32+c33)+(c12+c13+c42+c43)=第二列+第三列=68
因此(c22+c23+c32+c33)=34

由此得到s=34*9=306

newkid · 发表于 2011-9-15 22:15

虽然这个题完全不用SQL, 但是利用SQL找出所有幻方也算意外收获。
一开始我写AND n1.s1 + n2.s1=34 半天出不来，估计走NESTED LOOPS了，改成AND n1.s1=34 - n2.s1才能HASH JOIN.

solomon_007 · 发表于 2011-9-16 00:54

原帖由 newkid 于 2011-9-15 22:09 发表
S=(c11+c12+c21+c22)+(c12+c13+c22+c23)+(c13+c14+c23+c24)
+(c21+c22+c31+c32)+(c22+c23+c32+c33)+(c23+c24+c33+c34)
+(c31+c32+c41+c42)+(c32+c33+c42+c43)+(c33+c34+c43+c44)
对换位置：
(c11+c12+c13+c14)+(c21+c22+c23+c24)
+(c31+c32+c33+c34)+(c41+c42+c43+c44)
+(c12+c22+c32+c42)
+(c13+c23+c33+c43)
+(c21+c22+c23+c24)+(c31+c32+c33+c34)
+(c22+c23+c32+c33)

除了最后四个，其他的和都是34。
最后四个是中间的四个数，加上四个角就等于两条对角线：

(c22+c23+c32+c33)+C11+C14+C41+C44 = 68

这两条对角线之和也等于第一+第四行之和：
(c12+c13+c42+c43)+C11+C14+C41+C44 = 68

得到(c22+c23+c32+c33)=(c12+c13+c42+c43)
而(c22+c23+c32+c33)+(c12+c13+c42+c43)=第二列+第三列=68
因此(c22+c23+c32+c33)=34

由此得到s=34*9=306

我先想了半天，发现中间的出现了3次，4个角1次，其他2次，没有想到加4个角正好是两条对角线之和，就放弃了进一步思考。。。

真佩服！！

solomon_007 · 发表于 2011-9-16 00:57

原帖由 newkid 于 2011-9-15 22:15 发表
虽然这个题完全不用SQL, 但是利用SQL找出所有幻方也算意外收获。
一开始我写AND n1.s1 + n2.s1=34 半天出不来，估计走NESTED LOOPS了，改成AND n1.s1=34 - n2.s1才能HASH JOIN.

这个在调试是也碰到了，还觉的奇怪呢，没分析执行计划，就还原你的写法了。。。

solomon_007 · 发表于 2011-9-16 01:02

原帖由 newkid 于 2011-9-15 21:36 发表

别的不知道，反正四阶的很容易证明是常数，等会有空来写一下。
你那个高尔夫的SQL呢？我不是答应给你5万P币了么？

我看到了，试了一下，没搞出来，这个周末有时间再分析一下。。。

newkid · 发表于 2011-9-21 23:43

这周的题很简单。

Digital Watch

You have a digital watch which works on a 24-hour setup and shows hours and minutes. Looking at the watch at a certain time, you make the following observations:

. If the four figures on the watch are read from left to right, you get a prime number.
. Each figure, is larger than the figure to its left. (ex. 03:56, 13:49)

Both observations were valid eight minutes ago; and they will be valid one hour later.

What time is it?

WITH d AS (
SELECT LPAD(LEVEL,4,'0') s,LEVEL n FROM DUAL CONNECT BY LEVEL<=2359
)
,d2 AS (
SELECT s
FROM d
WHERE SUBSTR(s,1,1)<SUBSTR(s,2,1) AND SUBSTR(s,2,1)<SUBSTR(s,3,1) AND SUBSTR(s,3,1)<SUBSTR(s,4,1)
   AND SUBSTR(s,3)<='59'
   AND NOT EXISTS (SELECT NULL FROM d d2 WHERE d2.n>1 AND d2.n<=SQRT(d.n) AND MOD(d.n,d2.n)=0)
)
SELECT d2.s
   ,TO_CHAR(TO_DATE(d2.s,'HH24MI')+8/(24*60),'HH24:MI') current_time
  FROM d2,d2 d3
WHERE TO_CHAR(TO_DATE(d2.s,'HH24MI')+8/(24*60)+1/24,'HH24MI') = d3.s
;

S             CURRE
---------------- -----
0149          01:57
0239          02:47
0349          03:57

newkid · 发表于 2011-9-24 00:16

第六题(36楼)找到一个可能答案1; 0是否为答案不能确定。
题目：
25位选手参加象棋锦标赛。任意选取五位，其中至少有一位选手和其他四位选手在以前比赛过。
假设某选手和其他所有24位选手以前比赛过，这样的选手最小的可能数字是多少？
变通为：
在平面上25点之间画连线，已知任意选取5个点，其中必有一点和其他四点都有连线。
某点和其他24点之间都有连线，这样的点最少可能有几个？

人肉证明1是可能的答案：
假设某个点P和其他24点都有连线，则所有包含P点的5点组合全部满足条件。我们只需考察剩下的24点中任取5点是否也满足条件。
现在只需在剩下的24点间画线，使得所有点的连线不超过22条(最多22条, 这样加上到P点的连线也只有23条)，同时满足题目中的任选5点的要求。
画线方法：把24个点两两分组，共分12组。
除了同组的点，到其他组所有的点都画上连线。这样每个点就有22条连线，仅和一个点（同组点）之间没有连。
现在要证明这样画线的结果，任选5点都必有一点和其他四点有连线。
任取5点, 观察其中任意一点，因为它最多只能和一点不连（同组），所以仅存在以下两种可能：
1.这个点和其他四点全部相连；
2.这个点和其中一点不连，和其他三点相连。
用反证法，假设存在这样一个不满足题意的5点组合，则5个点都必须能够找到一个同组的点（不连）。因为同组的点必须两两配对，而5是奇数，所以这种情况不存在。

〇〇 · 发表于 2011-9-28 19:53

No: 10 September 28, 2011

Prime Neighbors

All of the numerals in a number are different than each other.

For all the neighboring numeral pairs in this number, the number formed by these neighboring numerals or its consecutive is a prime number.

What is the largest number satisfying these conditions?

Example: 1029. Pairs: “10” (11 is prime); “02” (both 2 and 3 are primes) and 29 (29 is prime).

[ You can answer this problem starting from Thursday at 11:00 (GMT) ]

newkid · 发表于 2011-9-28 23:52

第10题：素数邻居

有一个整数每位各不相同，取其中任意两位连续数字，要么它是个素数，要么它的后续数(+1)是个素数。满足这种条件的最大数是多少？
比如1029, 10+1=11是素数，02是素数（02+1=3也是素数），29也是素数。

很简单，把100以内的素数弄出来凑一凑就行。我怀疑CONNECT BY都能搞定。

WITH p AS (
SELECT n
FROM (SELECT LEVEL n FROM DUAL WHERE LEVEL>1 CONNECT BY LEVEL<100)
WHERE NOT EXISTS (SELECT 1 FROM DUAL WHERE LEVEL>1 AND MOD(n,LEVEL)=0 CONNECT BY LEVEL<n )
)
,p2 AS (
SELECT LPAD(n,2,'0') n FROM p UNION SELECT LPAD(n-1,2,'0') FROM p
)
,t(num) AS (
SELECT CAST(n AS VARCHAR2(10)) FROM p2 WHERE n>'09'
UNION ALL
SELECT t.num||SUBSTR(p2.n,2)
FROM t,p2
WHERE SUBSTR(t.num,-1,1)=SUBSTR(p2.n,1,1) AND INSTR(t.num,SUBSTR(p2.n,2))=0
)
SELECT * FROM (SELECT * FROM t ORDER BY TO_NUMBER(num) DESC) WHERE ROWNUM=1
;

NUM
---------------------------
8897361052

Elapsed: 00:00:00.53

第六题的人肉证明方法我也想出来了，挺啰嗦的。有空来写一下。

newkid · 发表于 2011-9-29 00:14

本帖最后由 newkid 于 2011-9-29 05:05 编辑

上面有BUG,每两位都不能相同。

WITH p AS (
SELECT n
  FROM (SELECT LEVEL n FROM DUAL WHERE LEVEL>1 CONNECT BY LEVEL<100)
WHERE NOT EXISTS (SELECT 1 FROM DUAL WHERE LEVEL>1 AND MOD(n,LEVEL)=0 CONNECT BY LEVEL<n )
)
,p2 AS (
SELECT * FROM (SELECT LPAD(n,2,'0') n FROM p UNION SELECT LPAD(n-1,2,'0') FROM p) WHERE SUBSTR(n,1,1)<>SUBSTR(n,2,1)
)
,t(num) AS (
SELECT CAST(n AS VARCHAR2(10)) FROM p2 WHERE n>'09'
UNION ALL
SELECT t.num||SUBSTR(p2.n,2)
  FROM t,p2
WHERE SUBSTR(t.num,-1,1)=SUBSTR(p2.n,1,1) AND INSTR(t.num,SUBSTR(p2.n,2))=0
)
SELECT * FROM (SELECT * FROM t ORDER BY TO_NUMBER(num) DESC) WHERE ROWNUM=1
;

NUM
----------------------------
5978361042

Elapsed: 00:00:00.49

WITH p AS (
SELECT n
FROM (SELECT LEVEL n FROM DUAL WHERE LEVEL>1 CONNECT BY LEVEL<100)
WHERE NOT EXISTS (SELECT 1 FROM DUAL WHERE LEVEL>1 AND MOD(n,LEVEL)=0 CONNECT BY LEVEL<n )
)
,p2 AS (
SELECT LPAD(n,2,'0') n FROM p UNION SELECT LPAD(n-1,2,'0') FROM p
)
,s AS (SELECT REPLACE(SYS_CONNECT_BY_PATH(SUBSTR(n,1,1),','),',')||SUBSTR(n,2,1) str
  FROM p2
START WITH n>'09'
CONNECT BY NOCYCLE SUBSTR(n,1,1)=PRIOR SUBSTR(n,2,1)
)
SELECT * FROM (
SELECT s.str
  FROM s,(SELECT TO_CHAR(LEVEL-1) n FROM DUAL CONNECT BY LEVEL<=10)
WHERE INSTR(s.str,n)>0
GROUP BY s.str
HAVING COUNT(DISTINCT n)=LENGTH(s.str)
ORDER BY TO_NUMBER(s.str) DESC
)
WHERE ROWNUM=1;

STR
---------------
5978361042

Elapsed: 00:00:04.63

[精华] puzzleup 2011