PUZZLEUP 2014

newkid · 发表于 2014-10-9 03:59

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

方法一：

我看了一下你的MODEL, 和我的代码是一样的思路，也就是说无法证明。其中TMP是不必要的，可以去掉：

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 )
            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()])]
               ,STR[ITERATION_NUMBER,S] = CASE WHEN YN[CV(),CV()] IS NULL THEN STR[CV(),CV()] END
            )
         )
SELECT COUNT(STR) FROM T2

COUNT(STR)
----------
   1625

Elapsed: 00:01:12.00

速度很慢, 因为你里面有嵌套循环。
改良一下，改用一系列标志位来表示占用与否：
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
         )
,t3 AS (
         SELECT * FROM t1
         MODEL
         DIMENSION BY (str s)
         MEASURES(n,str,str12,str23,str34,str45,0 n12,0 n23,0 n34,0 n45)
         RULES (
            n12[any]=n[str12[cv()]]
         ,n23[any]=n[str23[cv()]]
         ,n34[any]=n[str34[cv()]]
         ,n45[any]=n[str45[cv()]]
         )
      )
,t2 AS (
            SELECT * FROM T3
            MODEL
            DIMENSION BY (N)
            MEASURES(STR, N12 , N23  , N34  , N45 , 0 YN)
            RULES  ITERATE(3125) (
               STR[ITERATION_NUMBER] = CASE WHEN YN[ITERATION_NUMBER]=0 THEN STR[CV()] END
            ,YN[N12[ITERATION_NUMBER]]=CASE WHEN STR[ITERATION_NUMBER] IS NULL THEN YN[N12[ITERATION_NUMBER]] ELSE 1 END
            ,YN[N23[ITERATION_NUMBER]]=CASE WHEN STR[ITERATION_NUMBER] IS NULL THEN YN[N23[ITERATION_NUMBER]] ELSE 1 END
            ,YN[N34[ITERATION_NUMBER]]=CASE WHEN STR[ITERATION_NUMBER] IS NULL THEN YN[N34[ITERATION_NUMBER]] ELSE 1 END
            ,YN[N45[ITERATION_NUMBER]]=CASE WHEN STR[ITERATION_NUMBER] IS NULL THEN YN[N45[ITERATION_NUMBER]] ELSE 1 END
            )
   )
SELECT COUNT(STR) FROM T2;

COUNT(STR)
----------
   1625

Elapsed: 00:00:00.25

〇〇 · 发表于 2014-10-9 08:44

newkid 发表于 2014-10-9 02:48
用SQL找了一下，似乎8个就是最少的了。我的SQL只是挑选平方数组合，再根据一个简单的规则做了过滤，最后还 ...

http://blog.csdn.net/flyingscv/article/details/1932191

newkid · 发表于 2014-10-9 09:07

〇〇发表于 2014-10-9 08:44
http://blog.csdn.net/flyingscv/article/details/1932191

两个问题差远了，既不是正方形，也不要求大小各异。

peter1166 · 发表于 2014-10-10 21:03

newkid 发表于 2014-10-9 03:59
我看了一下你的MODEL, 和我的代码是一样的思路，也就是说无法证明。其中TMP是不必要的，可以去掉：

WI ...

newkid ，谢谢你的指点。你的思路我偷学了。
如何证明这个是最大的数，这种A到E的排列顺序只能是这个数了，字符的排列顺序不一样，结果不一样，
但是这个排序有 3125！种，太多了无法一一验证证明。
目前发现下面两种是 1625 ，
ORDER BY T1.L,T2.L,T3.L,T4.L,T5.L
ORDER BY T1.L,T2.L,T3.L,T4.L,T5.L desc
其他的尝试了很多，没发现比这个大的。
ORDER BY dbms_random.value

lugionline · 发表于 2014-10-13 07:06

本帖最后由 lugionline 于 2014-10-13 07:50 编辑

peter1166 发表于 2014-10-10 21:03
newkid ，谢谢你的指点。你的思路我偷学了。
如何证明这个是最大的数，这种A到E的排列顺序只能是 ...

这个是不是就证明了贪婪法是不可行的，只是恰好得到了答案？因为按另一种次序就有可能得到错误答案。
也许可以证明像 ABC,ACB,BAC,BCA,CAB,CBA这样的点构成的图是二分图，然后找出最大匹配，最后算出最大独立集

http://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Finding_maximum_independent_sets

其实也不一定要证明就是二分图，因为如果不是二分图，那问题就是NP-HARD，但既然提问人已经知道答案了

peter1166 · 发表于 2014-10-13 08:47

lugionline 发表于 2014-10-13 07:06
这个是不是就证明了贪婪法是不可行的，只是恰好得到了答案？因为按另一种次序就有可能得到错误答案。
也 ...

题目上已经说，如果问题问的是利用字母A,B,C产生的三字母代码，那么答案是18。
验证了只有顺序排序才能得到这个这个18 ，那是不是提示了这个顺序可以得到最大值。

peter1166 · 发表于 2014-10-15 14:04

第11题，不知道 newkid 是不是也到这里。

逻辑只有下面2个；
1、小正方形面积总和等于 18*19
2、任意两个小正方形边合计不能大于19
从3层开始一层一层往上加，到6层出来结果了，但明显不能组成 18*19 的长方形。
所有把那个  4*4 手工分解为 2*2*4 。
最后答案就是 10 9 9 8 2 2 2 2  。8个。

WITH T AS (SELECT LEVEL N ,LEVEL*LEVEL N2 FROM DUAL CONNECT BY LEVEL <= 18 )
SELECT T1.N , T2.N , T3.N ,T4.N ,T5.N
   ,T1.N2 , T2.N2 , T3.N2 ,T4.N2 ,T5.N2
FROM T T1, T T2 , T T3 ,T T4 ,T T5
WHERE T1.N2 + T2.N2 + T3.N2 + T4.N2 + T5.N2 = 18*19
AND T1.N >= T2.N AND T2.N >= T3.N AND T3.N >= T4.N AND T4.N >= T5.N
AND T1.N + T2.N <= 19
AND T1.N + T3.N <= 19
AND T2.N + T3.N <= 19
AND T1.N + T4.N <= 19
AND T2.N + T4.N <= 19
AND T3.N + T4.N <= 19
AND T1.N + T5.N <= 19
AND T2.N + T5.N <= 19
AND T3.N + T5.N <= 19
AND T4.N + T5.N <= 19
;

      N       N       N       N       N       N2       N2       N2       N2       N2
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
      10       9       9       8       4       100       81       81       64       16

〇〇 · 发表于 2014-10-15 14:12

peter1166 发表于 2014-10-15 14:04
第11题，不知道 newkid 是不是也到这里。

逻辑只有下面2个；

用递归能出来？

peter1166 · 发表于 2014-10-15 14:42

〇〇发表于 2014-10-15 14:12
用递归能出来？

递归还没试过。
小正方形在长方形内的充要条件不知道，我的穷举法弄不出来。
如果，用Model做个二维数组先画个大长方形，再用递归一个一个切，不知道行不行。

〇〇 · 发表于 2014-10-15 22:32

No: 12 October 15, 2014

Binary Digits

Insert 5 commas between the digits of 21218453415461109221 and obtain 6 numbers, so that no two consecutive digits will be the same in the binary representation of these numbers.

What is the sum of these 6 numbers?

If the problem was asked for 542 with one comma, then the answer would be 47 (5+42=47).

The binary representation of 5 is 101, the binary representation of 42 is 101010, and no two consecutive digits are the same in these numbers.

二进制数字

往21218453415461109221的数字中间插入5个逗号并获得6个数，以便这些数的二进制表示中不存在两个连续的相同数字。

这6个数的总和是多少？

如果这个问题改为542和一个逗号，那么答案是47（5+42=47）。

5的二进制表示为101，42的二进制表示是101010，在这些数字中都不存两个连续的相同数字。