PUZZLEUP 2014

peter1166 · 发表于 2014-10-2 22:22

newkid 发表于 2014-10-2 22:03
你这“块数”的公式是什么意思？(4*4*4*4) / (4*4) , (5*5*5*5*5) / (5*5)

以4个的为例子，下面每个 N 是一个块，每个块里有  1+2+3+4 个满足要求的意识。


SELECT (T1.N-1)*4+T2.N N
   , LISTAGG(T1.S||T2.S||T3.S||T4.S,',')WITHIN GROUP (ORDER BY T4.N) STR
FROM  (SELECT LEVEL N , CHR(LEVEL+64) S FROM DUAL CONNECT BY LEVEL <= 4) T1
   ,(SELECT LEVEL N , CHR(LEVEL+64) S FROM DUAL CONNECT BY LEVEL <= 4) T2
   ,(SELECT LEVEL N , CHR(LEVEL+64) S FROM DUAL CONNECT BY LEVEL <= 4) T3
   ,(SELECT LEVEL N , CHR(LEVEL+64) S FROM DUAL CONNECT BY LEVEL <= 4) T4
GROUP BY T1.N , T2.N , T3.N ;

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

peter1166 · 发表于 2014-10-2 22:54

newkid 发表于 2014-10-2 22:03
你这“块数”的公式是什么意思？(4*4*4*4) / (4*4) , (5*5*5*5*5) / (5*5)

我的错了，一个块里不一定10个，

1 AAAA,AAAB,AAAC,AAAD
1       ,AABB,AABC,AABD
1       ,       ,AACC,AACD
1       ,       ,    ,AADD
---------------------
2 ABAA, , ,
2 ABBA,ABBB,ABBC,ABBD
2 ABCA, ,ABCC,ABCD
2 ABDA, , ,ABDD
---------------------
3 ACAA,ACAB, ,
3    ,ACBB, ,
3 ACCA,ACCB,ACCC,ACCD
3 ACDA,ACDB, ,ACDD
---------------------
4 ADAA,ADAB,ADAC,
4    ,ADBB,ADBC,
4    , ,ADCC,
4 ADDA,ADDB,ADDC,ADDD
---------------------
5    ,BAAB,BAAC,BAAD
5    , , ,
5    ,BACB, ,
5    ,BADB,BADC,
---------------------
6 BBAA,BBAB,BBAC,BBAD
6    ,BBBB,BBBC,BBBD
6    , ,BBCC,BBCD
6    , , ,BBDD
---------------------
7 BCAA, ,BCAC,BCAD
7 BCBA,BCBB, ,
7    ,BCCB,BCCC,BCCD
7    ,BCDB, ,BCDD
---------------------
8 BDAA, , ,BDAD
8 BDBA,BDBB,BDBC,
8 BDCA, ,BDCC,
8    ,BDDB,BDDC,BDDD
---------------------

udfrog · 发表于 2014-10-8 18:04

newkid 发表于 2014-10-1 22:25
从三个字母的来看是很有规律的，就是按顺序添加，不符合条件的丢弃。如果这样的话走一遍就得到结果了。但如 ...

证明？不会，但我坚信1625是对的。这样给章不。。。

udfrog · 发表于 2014-10-8 18:11

〇〇发表于 2014-10-2 07:17
你这个办法是对5个字母公平的,只要验证不包含在内的每个字符串都不符合那个规则

你这个结论显然不对。
newkid这套姿势，很像是对的，就在于“按顺序”导致了不会出现bab这种牌型，所以可以出现abb和bba，否则只能出现bab，这数量又怎么会一样。
我倒是觉得，是有一个命题--只要这套组合中不出现aba这种牌型，这套组合就一定是最大组合之一。

〇〇 · 发表于 2014-10-8 20:15

No: 11 October 08, 2014

Squares

You will dissect a 18x19 rectangle into squares.

-The sides of the squares will be integers.

-Squares need not to be of different sizes.

-Squares may not overlap.

-The number of the squares will be minimum.

Enter the sides of the squares from the smallest to the biggest separated with commas (Example: 2,3,3,3,6,….)

把18*19的矩形分成正方形。正方形的边长为整数，它们不一定大小不同，但不能互相覆盖，正方形的数量要最小。
把边长从小到大排列，用逗号隔开，例如2,3,3,3,6,
这个题我在一个数学竞赛书上见过，还有划分正方形的，但立方体是不能这样划分的

〇〇 · 发表于 2014-10-8 20:17

完美正方形_百科
[完美正方形]是指在一正方形内切割出大小都相异的小正方形。最早由莫伦提出。数学家们一度花了很大精力都无任何结果以至于1930年苏联著名数学家鲁金猜想不可能把一个正方形分割成有限个大小不同的正方形莫伦对此猜想提出了挑战并提供了一个解决思路如果同一个矩形有两个不同的正方形剖分且其中一个剖分的每个正方形都不 …

360百科.
baike.baidu.com/view/801280.htm 1 天前
.

newkid · 发表于 2014-10-8 21:58

先画出一个答案8，(2,2,2,2,8,9,9,10), 剩下的用SQL就好找了。

peter1166 · 发表于 2014-10-8 22:55

newkid 发表于 2014-10-1 22:25
从三个字母的来看是很有规律的，就是按顺序添加，不符合条件的丢弃。如果这样的话走一遍就得到结果了。但如 ...

第十题，  SQL 的弄出来了，  newkid  兄，你的答案是对的。证明如下；

方法一：
先用SQL　写了３个的，　没问题，　再做了４个的，也没问题　，　但是５个的　，报错了　ORA-01489: 字符串连接的结果过长
看到这个错误，　估计你能猜到我怎么弄的了，　如下；　

WITH T AS (SELECT LEVEL L  , CHR(LEVEL+64) C FROM DUAL CONNECT BY LEVEL <= 4 )
,T1 AS (
         SELECT ROW_NUMBER()OVER(ORDER BY T1.L,T2.L,T3.L,T4.L)-1 N
               ,T1.C||T2.C||T3.C||T4.C  STR
               ,T2.C||T1.C||T3.C||T4.C  STR12
               ,T1.C||T3.C||T2.C||T4.C  STR23
               ,T1.C||T2.C||T4.C||T3.C  STR34
         FROM T T1, T T2 , T T3 , T T4
         )
,T2 AS (
            SELECT * FROM T1
            MODEL
            DIMENSION BY (T1.N)
            MEASURES(T1.STR , T1.STR12 , T1.STR23 , T1.STR34 , 0 YN , '    ' S)
            RULES  ITERATE(256) (
               YN[ITERATION_NUMBER] = NVL(INSTR(LISTAGG(STR,',')WITHIN GROUP(ORDER BY STR)[N<CV()],STR34[CV()]),0)+
                                       NVL(INSTR(LISTAGG(STR,',')WITHIN GROUP(ORDER BY STR)[N<CV()],STR23[CV()]),0)+
                                       NVL(INSTR(LISTAGG(STR,',')WITHIN GROUP(ORDER BY STR)[N<CV()],STR12[CV()]),0)
               ,S[ITERATION_NUMBER] = CASE WHEN YN[CV()] = 0 THEN STR[CV()] END
               ,STR[ITERATION_NUMBER] = S[CV()]
            )
         )
SELECT COUNT(STR) FROM T2

--136

WITH T AS (SELECT LEVEL L  , CHR(LEVEL+64) C FROM DUAL CONNECT BY LEVEL <= 5 )
,T1 AS (
         SELECT ROW_NUMBER()OVER(ORDER BY T1.L,T2.L,T3.L,T4.L,T5.L)-1 N
               ,T1.C||T2.C||T3.C||T4.C||T5.C  STR
               ,T2.C||T1.C||T3.C||T4.C||T5.C STR12
               ,T1.C||T3.C||T2.C||T4.C||T5.C STR23
               ,T1.C||T2.C||T4.C||T3.C||T5.C STR34
               ,T1.C||T2.C||T3.C||T5.C||T4.C STR45
         FROM T T1, T T2 , T T3 , T T4  , T T5
         )
,T2 AS (
            SELECT * FROM T1
            MODEL
            DIMENSION BY (T1.N)
            MEASURES(T1.STR , T1.STR12 , T1.STR23 , T1.STR34 , T1.STR45 , 0 YN , '    ' S)
            RULES  ITERATE(3125) (
               YN[ITERATION_NUMBER] = NVL(INSTR(LISTAGG(STR,',')WITHIN GROUP(ORDER BY STR)[N<CV()],STR45[CV()]),0)+
                                       NVL(INSTR(LISTAGG(STR,',')WITHIN GROUP(ORDER BY STR)[N<CV()],STR34[CV()]),0)+
                                       NVL(INSTR(LISTAGG(STR,',')WITHIN GROUP(ORDER BY STR)[N<CV()],STR23[CV()]),0)+
                                       NVL(INSTR(LISTAGG(STR,',')WITHIN GROUP(ORDER BY STR)[N<CV()],STR12[CV()]),0)
               ,S[ITERATION_NUMBER] = CASE WHEN YN[CV()] = 0 THEN STR[CV()] END
               ,STR[ITERATION_NUMBER] = S[CV()]
            )
         )
SELECT COUNT(STR) FROM T2;

ORA-01489: 字符串连接的结果过长

上面的方法失败了！  想其他方法。

方法2 ：

WITH T AS (SELECT LEVEL L  , CHR(LEVEL+64) C FROM DUAL CONNECT BY LEVEL <= 5 )
,T1 AS (
         SELECT ROW_NUMBER()OVER(ORDER BY T1.L,T2.L,T3.L,T4.L,T5.L)-1 N
               ,T1.C||T2.C||T3.C||T4.C||T5.C  STR
               ,T2.C||T1.C||T3.C||T4.C||T5.C  STR12
               ,T1.C||T3.C||T2.C||T4.C||T5.C  STR23
               ,T1.C||T2.C||T4.C||T3.C||T5.C  STR34
               ,T1.C||T2.C||T3.C||T5.C||T4.C  STR45
         FROM T T1, T T2 , T T3 , T T4 , T T5
         )
,T2 AS (
            SELECT * FROM T1
            MODEL
            DIMENSION BY (T1.N,T1.STR S)
            MEASURES(T1.STR , T1.STR12 , T1.STR23  , T1.STR34  , T1.STR45 , CAST('' AS CHAR(5)) YN , CAST('' AS CHAR(5)) TMP )
            RULES  ITERATE(3125) (
               YN[ITERATION_NUMBER,S] = MAX(STR)[N<CV(),S IN (STR12[CV(),CV()],STR23[CV(),CV()],STR34[CV(),CV()],STR45[CV(),CV()])]
               ,TMP[ITERATION_NUMBER,S] = CASE WHEN YN[CV(),CV()] IS NULL THEN STR[CV(),CV()] END
               ,STR[ITERATION_NUMBER,S] = TMP[CV(),CV()]
            )
         )
SELECT COUNT(STR) FROM T2

-- 1625

成功！

newkid · 发表于 2014-10-8 23:23

peter1166 发表于 2014-10-8 22:55
第十题， SQL 的弄出来了， newkid 兄，你的答案是对的。证明如下；

方法一：

这方法能保证是最大集合？说明一下？

newkid · 发表于 2014-10-9 02:48

newkid 发表于 2014-10-8 21:58
先画出一个答案8，(2,2,2,2,8,9,9,10), 剩下的用SQL就好找了。

用SQL找了一下，似乎8个就是最少的了。我的SQL只是挑选平方数组合，再根据一个简单的规则做了过滤，最后还得人工考察能否拼成。
希望有人把拼凑步骤也用SQL写出来！

PUZZLEUP 2014

浏览过的版块