PUZZLEUP 2014

newkid · 发表于 2014-10-15 22:33

这个太简单了，这期的章算是白送的。

newkid · 发表于 2014-10-15 22:36

第11题我是用SQL试图找出少于7个的各种组合，结果没有一个能够拼成18*19的矩形：

WITH s AS (SELECT LEVEL n,LEVEL*LEVEL a FROM DUAL CONNECT BY LEVEL<=18) ---- 各种尺寸，从1到18
,s2 AS ( -------- 每种尺寸的所有可能个数，最多不超过7个
SELECT n
   ,cnt
   ,a*cnt AS a ------- 面积
  FROM s,(SELECT LEVEL cnt FROM DUAL CONNECT BY LEVEL<8)
WHERE a*cnt<=18*19
)
,t(n,cnt,a,path) AS ( ------ 递归找出各种尺寸以及不同个数的组合
SELECT n,cnt,a,CAST(n||'*'||cnt AS VARCHAR2(200)) path
  FROM s2
UNION ALL
SELECT s2.n,t.cnt+s2.cnt,t.a+s2.a,t.path||','||s2.n||'*'||s2.cnt
  FROM t,s2
WHERE t.n<s2.n
   AND t.cnt+s2.cnt<8
   AND t.a+s2.a<=18*19
)
,r AS ( ------ 所有拼起来总面积相符的组合，可能是答案
SELECT /*+ materialize */ ROWNUM id,cnt,path FROM t WHERE a=18*19 AND cnt<8
)
,r2 AS ( ---------- 每种尺寸的正方形拆成一行, 其个数为s_cnt
SELECT id,cnt
   ,TO_NUMBER(REGEXP_SUBSTR(str,'[^*]+',1,1)) s
   ,REGEXP_SUBSTR(str,'[^*]+',1,2) s_cnt
   ,path
  FROM (
SELECT r.*,REGEXP_SUBSTR(path,'[^,]+',1,n) str
  FROM r,(SELECT LEVEL n FROM DUAL CONNECT BY LEVEL<=8)
)
WHERE str IS NOT NULL
)
,r3 AS (
SELECT *
FROM (
   SELECT r3.*,SUM(CASE WHEN rn<=2 THEN s END) OVER(PARTITION BY id) sum2  ---- 每一组中最大的两个加起来不得越界
   FROM ( ---------- 把上述结果的每种正方形再拆成每个一行（每种有s_cnt行）
         SELECT id, path, id*100+n AS sq_id,cnt,s,ROW_NUMBER() OVER(PARTITION BY id ORDER BY s DESC) rn
         FROM r2,(SELECT LEVEL n FROM DUAL CONNECT BY LEVEL<=8)
         WHERE n<=s_cnt
         ) r3
   )
   WHERE sum2<=19
)
,t2(id,cnt,path,sq_id,s) AS ( ------- 每组答案中必定有几个正方形的边之和为18或者19
SELECT id,cnt,path,sq_id,s FROM r3
UNION ALL
SELECT t2.id,t2.cnt,t2.path,r3.sq_id,t2.s+r3.s FROM t2,r3 WHERE t2.id=r3.id AND t2.sq_id<r3.sq_id
)
SELECT cnt,path
  FROM t2
WHERE s IN (18,19)
GROUP BY id,path,cnt
HAVING COUNT(DISTINCT s)=2;

CNT PATH
----------------------
5 4*1,8*1,9*2,10*1
6 1*1,7*2,9*3
6 2*1,5*1,8*3,11*1
6 5*1,7*4,11*1
6 5*2,7*1,9*3
6 6*3,7*1,8*1,11*1
7 1*1,3*1,5*1,8*1,9*3
7 1*2,4*1,9*4
7 2*1,3*1,4*1,8*3,11*1
7 2*1,5*1,6*4,13*1
7 2*1,6*3,7*1,9*1,10*1
7 2*2,6*2,9*2,10*1
7 3*1,4*1,5*1,8*3,10*1
7 4*1,5*1,6*3,7*1,12*1
7 5*1,6*3,8*2,9*1
7 5*2,6*1,8*4
7 6*4,7*2,10*1

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

newkid 发表于 2014-10-15 22:33
这个太简单了，这期的章算是白送的。

把所有的01间隔二进制数找出来匹配?

newkid · 发表于 2014-10-15 22:46

〇〇发表于 2014-10-15 22:37
把所有的01间隔二进制数找出来匹配?

不用所有的，20位以内的就行。

〇〇 · 发表于 2014-10-16 08:58

〇〇发表于 2014-10-15 22:32
No: 12 October 15, 2014

Binary Digits

----
21,21845,341,5461,10922,1

select 21+21845+341+5461+10922+1 from dual;
38591
-----
declare
s number:=0;
s1 number:=1;
begin
for i in 1..10 loop
s:=s+power(2,2*i-1);
s1:=s/2;
dbms_output.put_line((i*2-1)||','||lpad('10',2*i,'10')||','||s1);
dbms_output.put_line((i*2)||','||lpad('01',2*i,'01')||','||s);
end loop;
end;
/
----------
1,10,1
2,01,2
3,1010,5
4,0101,10
5,101010,21
6,010101,42
7,10101010,85
8,01010101,170
9,1010101010,341
10,0101010101,682
11,101010101010,1365
12,010101010101,2730
13,10101010101010,5461
14,01010101010101,10922
15,1010101010101010,21845
16,0101010101010101,43690
17,101010101010101010,87381
18,010101010101010101,174762
19,10101010101010101010,349525
20,01010101010101010101,699050

peter1166 · 发表于 2014-10-16 10:25

第12题：

我是这么做的，可能会有更快的。

WITH T AS (
         SELECT N
         FROM (SELECT LEVEL N , FLOOR(LEVEL/2) SHR1 FROM DUAL CONNECT BY LEVEL <= 10E4)
         WHERE N + SHR1 - 2 * BITAND(N,SHR1) IN (SELECT POWER(2,LEVEL)-1 FROM DUAL CONNECT BY LEVEL <= 16)
      )
SELECT *
FROM T T1,T T2,T T3,T T4,T T5,T T6
WHERE T1.N||T2.N||T3.N||T4.N||T5.N||T6.N = '21218453415461109221'
AND ROWNUM <= 1 ;


      N       N       N       N       N       N
---------- ---------- ---------- ---------- ---------- ----------
      21    21845       341    5461    10922       1

peter1166 · 发表于 2014-10-16 10:33

本帖最后由 peter1166 于 2014-10-16 10:43 编辑

忘了，应该取合计。如下；
我的逻辑是，右移1位以后跟原数做 XOR ，如果都是 1 ，则满足条件，都是 1的有  POWER(2，n）-1 的数字，如 1,3,7,15，。。。

WITH T AS (
         SELECT N
         FROM (SELECT LEVEL N , FLOOR(LEVEL/2) SHR1 FROM DUAL CONNECT BY LEVEL <= 10E4)
         WHERE N + SHR1 - 2 * BITAND(N,SHR1) IN (SELECT POWER(2,LEVEL)-1 FROM DUAL CONNECT BY LEVEL <= 16)
      )
SELECT T1.N,T2.N,T3.N,T4.N,T5.N,T6.N
   , T1.N + T2.N  + T3.N + T4.N + T5.N + T6.N TTL
FROM T T1,T T2,T T3,T T4,T T5,T T6
WHERE T1.N||T2.N||T3.N||T4.N||T5.N||T6.N = '21218453415461109221'
AND ROWNUM <= 1 ;


      N       N       N       N       N       N       TTL
---------- ---------- ---------- ---------- ---------- ---------- ----------
      21    21845       341    5461    10922       1    38591

〇〇 · 发表于 2014-10-16 10:57

peter1166 发表于 2014-10-16 10:25
第12题：

我是这么做的，可能会有更快的。

2秒，很快

peter1166 · 发表于 2014-10-16 11:16

〇〇发表于 2014-10-16 10:57
2秒，很快

您的机器好啊，我这里5秒。
111,1111, 这样的做 not 运算的话就变 0 ，那样就不用 IN （）里的内容了会更快，
但是 Oracle 的 not 运算不知道怎么弄。

〇〇 · 发表于 2014-10-16 11:58

〇〇发表于 2014-10-16 10:57
2秒，很快

加了个条件 1.36秒
WITH T AS (
         SELECT N
         FROM (SELECT LEVEL N , FLOOR(LEVEL/2) SHR1 FROM DUAL CONNECT BY LEVEL <= 10E4)
         WHERE N + SHR1 - 2 * BITAND(N,SHR1) IN (SELECT POWER(2,LEVEL)-1 FROM DUAL CONNECT BY LEVEL <= 16)
      )
SELECT *
FROM T T1,T T2,T T3,T T4,T T5,T T6
WHERE t1.n like '2%' and T1.N||T2.N||T3.N||T4.N||T5.N||T6.N = '21218453415461109221'
AND ROWNUM <= 1 ;