puzzleup 2011

〇〇

n=4
字符串第一列出现的次数是
8a
4b
2c
1d
从第2行的第2列刚好是n=3的次序

〇〇

猜测n=26 AY

〇〇

因为A开头的比其他加起来还多一个，最后一个
即A+(N-1)

newkid

假设序号和为N的总个数为F(n), 以n=26为例，可以按开始字母分类：

Z开头：1个
A开头：F(n-1)个;
B开头：F(n-2)个;
.....

F(1) =1
F(n) = 1 + F(n-1) + F(n-2) +...+ F(1)
F(n-1) = 1 + F(n-2) + F(n-3) +...+ F(1)

F(n) - F(n-1) = F(n-1)

F(n) = 2* F(n-1) = 2^(N-1)

等比数列求和公式，SUM(F(1~n)) = F(n) + F(n-1) + F(n-2) +...+ F(1) = F(n+1)-1 = 2^N-1

用SQL验证当N=10:

WITH d AS (
SELECT CHR(64+LEVEL) c
      ,LEVEL n
  FROM DUAL
CONNECT BY LEVEL<=26
)
,t(str,s) AS (
SELECT CAST(c AS VARCHAR2(30))
      ,n
  FROM d
WHERE n<=10
UNION ALL
SELECT t.str||d.c
      ,t.s + d.n
  FROM t,d
WHERE t.s + d.n<=10
)
SELECT s,count(*) FROM t GROUP BY ROLLUP(s);

         S   COUNT(*)
---------- ----------
         1          1
         2          2
         3          4
         4          8
         5         16
         6         32
         7         64
         8        128
         9        256
        10        512
                 1023

------------------------- 昨天就想到这里。今天正想解决排序问题，没想到OO一眼看穿了：
在F(n)里面，以A开头个数为 F(n-1);
在F(n-1)里面，以A开头个数为 F(n-2);
....
所以所有以A开头的总个数,
SUM(FA(1~n)) = F(n-1) + F(n-2) +...+ F(1) + 1 = F(n) = 2^(N-1)

验证N=10:
WITH d AS (
SELECT CHR(64+LEVEL) c
      ,LEVEL n
  FROM DUAL
CONNECT BY LEVEL<=26
)
,t(str,s) AS (
SELECT CAST(c AS VARCHAR2(30))
      ,n
  FROM d
WHERE n<=10
UNION ALL
SELECT t.str||d.c
      ,t.s + d.n
  FROM t,d
WHERE t.s + d.n<=10
)
SELECT s,count(*) CNT,COUNT(CASE WHEN str LIKE 'A%' THEN 1 END) CNTA
FROM t GROUP BY ROLLUP(s);

         S        CNT       CNTA
---------- ---------- ----------
         1          1          1
         2          2          1
         3          4          2
         4          8          4
         5         16          8
         6         32         16
         7         64         32
         8        128         64
         9        256        128
        10        512        256
                 1023        512

因此中间那个就是以A开头的最大编码，即N=26时为AY.

〇〇

newkid 发表于 2011-11-10 22:37
假设序号和为N的总个数为F(n), 以n=26为例，可以按开始字母分类：

Z开头：1个

终于有证明而不是猜测了

newkid

#17 Red and Black Squares
You will paint a canvas, consisting of AxA squares. Each square in this grid will be painted either red or black. For every possible painting under this rule, you are able to pick 2 rows and 2 columns in such a way that the four squares on their intersections have the same color. What is the possible minimum value of A?

AxA的方格涂上红黑两种颜色，不管怎么涂，你都可以找到两行两列，使得交叉点为同一种颜色。A可能的最小值为多少？

A的最小值不能为3, 因为存在这种涂法：
001
010
011

任意两行、两列的交叉点都包含了两种颜色。

newkid

暴力强攻，看看 N=4 时行不行：
VAR N NUMBER;
EXEC :N:=4;

WITH t AS ( ----- 构造从 0 - 2^:N - 1 中任选 :N 个 的所有组合。把二进制字符串用十进制表示方便下面的加法运算
SELECT /*+ MATERIALIZE */
       str,SUBSTR(str,(n-1)*:N+1,4) c,:N n  
  FROM (
         SELECT REPLACE(SYS_CONNECT_BY_PATH(STR,','),',') str ------- 从所有0,1的N位排列中任选N个
           FROM (
                  SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') str ----- 构造0,1的所有N位排列
                    FROM (SELECT 1 n FROM DUAL UNION ALL SELECT 0 FROM DUAL)
                   WHERE LEVEL=:N
                  CONNECT BY LEVEL<=:N
                )
         WHERE LEVEL=:N
         CONNECT BY str>PRIOR str
                 AND LEVEL<=:N
        )
      ,(SELECT LEVEL n FROM DUAL CONNECT BY LEVEL<=:N)  ------ 将结果拆成N行一组
)
SELECT t1.str
FROM t t1,t t2   -------- 将组内成员两两组合，检验
WHERE t1.str=t2.str
      AND t1.c<t2.c
      AND NVL(REPLACE(LPAD(t1.c+t2.c,:N,'0'),'1'),'0') IN ('0','2','20','02') ------- 如果相加之后某位=1则说明颜色不同；颜色相同必为0或2. 如果的两两任意组合，最后剩下0或2不多于一个，则所有交叉点都含两种颜色，就找到一个反例
GROUP BY t1.str
HAVING COUNT(*)=:N*(:N-1)/2  -------- C(:N,2)
;


STR
-----------------------
0011010110011010
0011010110101100
0101011010001011
0110100110101100
0010010110011110
0011010010011110
0100011110011010
0001011010101101
0001011110101100
0101011010101100
0001011010111100
0010010110111100
0011010010011010
0011010110011110
0011010101101000
0011010101101001
0011010101101010
0011011010101101
0101011010011100
0011100110101100
0001011010101100
0011010110001110
0101011010011010
0011010010101101
0101100110101100
0011010101101100
0011011010001101
0011011010011100
0101011010111100
0010010110011100
0011010110011100
0011011010011010
0111100110101100
0010011110011100
0011011010101100

35 rows selected.

有35种违反规定的涂法。

再试 N=5:

EXEC :N:=5;

no rows selected

Elapsed: 00:00:24.74

这个最小值就是5.

newkid

改良的暴力法：（和平解决办法留给OO去想）

把判断放到递归里面，一旦发现有同颜色的交叉点就及时中断。注意递归里面使用嵌套表的新玩法，这是我的最新研究成果。

EXEC :N:=4;

WITH b AS (
     SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') str ----- 构造0,1的所有N位排列
       FROM (SELECT 1 n FROM DUAL UNION ALL SELECT 0 FROM DUAL)
      WHERE LEVEL=:N
     CONNECT BY LEVEL<=:N
)
,t(lvl,all_str,str) AS (
SELECT 1,KU$_VCNT(str),str FROM b
UNION ALL
SELECT t.lvl+1
      ,t.all_str MULTISET UNION KU$_VCNT(b.str)
      ,b.str
  FROM t,b
WHERE t.lvl<:N
       AND t.str<b.str
       AND NOT EXISTS (SELECT 1 FROM TABLE(t.all_str) WHERE NVL(REPLACE(LPAD(COLUMN_VALUE+b.str,:N,'0'),'1'),'0') NOT IN ('0','2','20','02'))
)
SELECT all_str FROM t WHERE lvl=:N;


ALL_STR
--------------------------------------------
KU$_VCNT('0011', '0101', '0110', '1000')
KU$_VCNT('0011', '0101', '0110', '1001')
KU$_VCNT('0011', '0101', '0110', '1010')
KU$_VCNT('0011', '0101', '0110', '1100')
KU$_VCNT('0011', '0101', '1000', '1110')
KU$_VCNT('0011', '0110', '1000', '1101')
KU$_VCNT('0101', '0110', '1000', '1011')
KU$_VCNT('0011', '0100', '1001', '1010')
KU$_VCNT('0011', '0100', '1001', '1110')
KU$_VCNT('0010', '0111', '1001', '1100')
KU$_VCNT('0100', '0111', '1001', '1010')
KU$_VCNT('0011', '0110', '1001', '1010')
KU$_VCNT('0011', '0110', '1001', '1100')
KU$_VCNT('0101', '0110', '1001', '1010')
KU$_VCNT('0101', '0110', '1001', '1100')
KU$_VCNT('0011', '0101', '1001', '1010')
KU$_VCNT('0011', '0101', '1001', '1100')
KU$_VCNT('0011', '0101', '1001', '1110')
KU$_VCNT('0010', '0101', '1001', '1100')
KU$_VCNT('0010', '0101', '1001', '1110')
KU$_VCNT('0011', '0100', '1010', '1101')
KU$_VCNT('0011', '1001', '1010', '1100')
KU$_VCNT('0101', '1001', '1010', '1100')
KU$_VCNT('0110', '1001', '1010', '1100')
KU$_VCNT('0111', '1001', '1010', '1100')
KU$_VCNT('0001', '0111', '1010', '1100')
KU$_VCNT('0011', '0110', '1010', '1100')
KU$_VCNT('0011', '0110', '1010', '1101')
KU$_VCNT('0101', '0110', '1010', '1100')
KU$_VCNT('0001', '0110', '1010', '1100')
KU$_VCNT('0001', '0110', '1010', '1101')
KU$_VCNT('0011', '0101', '1010', '1100')
KU$_VCNT('0010', '0101', '1011', '1100')
KU$_VCNT('0101', '0110', '1011', '1100')
KU$_VCNT('0001', '0110', '1011', '1100')

35 rows selected.

Elapsed: 00:00:00.02

EXEC :N:=5;

/

Elapsed: 00:00:00.06

速度快这么多？

sohay

看newkid写的sql，真算的是sql界的一朵奇葩啊，各种玩法，各种新花样，看的人眼花缭乱

newkid

嵌套表在这里是没有必要的，用传统的拼接、解析字符串就可以：

WITH b AS (
  SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') str
   FROM (SELECT 1 n FROM DUAL UNION ALL SELECT 0 FROM DUAL)
   WHERE LEVEL=:N
   CONNECT BY LEVEL<=:N
)
,t(lvl,all_str,str) AS (
SELECT 1,CAST(str AS VARCHAR2(30)),str FROM b
UNION ALL
SELECT t.lvl+1
      ,t.all_str||b.str
      ,b.str
FROM t,b
WHERE t.lvl<:N
      AND t.str<b.str
      AND NOT EXISTS (SELECT 1
                       FROM DUAL
                       WHERE NVL(REPLACE(LPAD(SUBSTR(t.all_str,(LEVEL-1)*:N+1,:N)+b.str,:N,'0'),'1'),'0')
                             NOT IN ('0','2','20','02')
                       CONNECT BY LEVEL<=t.lvl
                     )
)
SELECT all_str FROM t WHERE lvl=:N;

这道题的人肉证明办法也想出来了，就是有些啰嗦。