puzzleup 2018

〇〇

〇〇 发表于 2018-11-9 14:01
这样就不快了
MIN(ABS(S1.STR-S2.STR)) MAX(ABS(S1.STR-S2.STR))
----------------------- ----------- ...

分别求最大最小差，然后合并就快多了

WITH n as (select to_char(level-1) n,power(2,level-1) b from dual connect by level<=10)
,ddmm as (
select dm,sum(b) b
   from (select to_char(date '2001-1-1'+level-1,'ddmm') dm from dual connect by level<=365)
       ,n
   where instr(dm,n)>0
group by dm having count(*)=4
)      
,hhmi as (
select hhmi,sum(b) b
  from (select to_char(date '2001-1-1'+level/(24*60),'hh24mi') hhmi from dual connect by level<24*60)
      ,n
   where instr(hhmi,n)>0
group by hhmi having count(*)=4
)
,ddmmhhmi as (
select dm,hhmi,trunc(log(2,b)) b1,round(log(2,b-power(2,trunc(log(2,b))))) b2
  from (select dm,hhmi,power(2,10)-1-ddmm.b-hhmi.b b from ddmm,hhmi
        where bitand(ddmm.b,hhmi.b)=0
       )
),
s as(select min(str)mins,max(str)maxs from (
select dm||decode(n,1,b1||b2,b2||b1)||hhmi as str
  from ddmmhhmi,(select * from n where n<2)
)),
s1 as(select min(a.hhmi-b.hhmi)minh from hhmi a,hhmi b where a.b=b.b and a.hhmi>b.hhmi)
select maxs-mins,minh from s,s1
;

MAXS-MINS       MINH
---------- ----------
1501979184          9

Elapsed: 00:00:00.57

solomon_007

〇〇 发表于 2018-11-9 14:05
分别求最大最小差，然后合并就快多了

WITH n as (select to_char(level-1) n,power(2,level-1) b from ...

要快一点点

SQL> set timing on;
SQL>
SQL> WITH n as (select to_char(level-1) n,power(2,level-1) b from dual connect by level<=10)
  2   ,ddmm as (
  3   select dm,sum(b) b
  4      from (select to_char(date '2001-1-1'+level-1,'ddmm') dm from dual connect by level<=365)
  5          ,n
  6      where instr(dm,n)>0
  7   group by dm having count(*)=4
  8   )
  9   ,hhmi as (
10  select hhmi,sum(b) b
11    from (select to_char(date '2001-1-1'+level/(24*60),'hh24mi') hhmi from dual connect by level<24*60)
12        ,n
13     where instr(hhmi,n)>0
14  group by hhmi having count(*)=4
15  )
16  ,ddmmhhmi as (
17  select dm,hhmi,trunc(log(2,b)) b1,round(log(2,b-power(2,trunc(log(2,b))))) b2
18    from (select dm,hhmi,power(2,10)-1-ddmm.b-hhmi.b b from ddmm,hhmi
19          where bitand(ddmm.b,hhmi.b)=0
20         )
21  ),
22  s as (
23  select str from (
24  select dm||decode(n,1,b1||b2,b2||b1)||hhmi as str
25    from ddmmhhmi,(select * from n where n<2)
26  ))
27  select x.min_diff,y.max_diff
28    from ( select min(s1.str - s2.str) min_diff
29              from s s1, s s2
30             where s1.str > s2.str) x,
31   (select max(s.str)-min(s.str) max_diff from s) y
32  /
  MIN_DIFF   MAX_DIFF
---------- ----------
         9 1501979184
Executed in 0.954 seconds

SQL>
SQL>
SQL>
SQL> WITH n as (select to_char(level-1) n,power(2,level-1) b from dual connect by level<=10)
  2   ,ddmm as (
  3   select dm,sum(b) b
  4      from (select to_char(date '2001-1-1'+level-1,'ddmm') dm from dual connect by level<=365)
  5          ,n
  6      where instr(dm,n)>0
  7   group by dm having count(*)=4
  8   )
  9   ,hhmi as (
10  select hhmi,sum(b) b
11    from (select to_char(date '2001-1-1'+level/(24*60),'hh24mi') hhmi from dual connect by level<24*60)
12        ,n
13     where instr(hhmi,n)>0
14  group by hhmi having count(*)=4
15  )
16  ,ddmmhhmi as (
17  select dm,hhmi,trunc(log(2,b)) b1,round(log(2,b-power(2,trunc(log(2,b))))) b2
18    from (select dm,hhmi,power(2,10)-1-ddmm.b-hhmi.b b from ddmm,hhmi
19          where bitand(ddmm.b,hhmi.b)=0
20         )
21  ),
22  s as (
23  select str from (
24  select dm||decode(n,1,b1||b2,b2||b1)||hhmi as str
25    from ddmmhhmi,(select * from n where n<2)
26  ))
27  select min(s1.str - s2.str),max(s1.str - s2.str)
28    from s s1, s s2
29   where s1.str > s2.str
30  /
MIN(S1.STR-S2.STR) MAX(S1.STR-S2.STR)
------------------ ------------------
                 9         1501979184
Executed in 1.407 seconds

SQL>

newkid

#16 RECTANGLES

You have N rectangles (N > 1). The 2N numbers used by the length of short and long edges of these rectangles are all different positive integers.

You can create a larger rectangle by using all of these rectangles. The large rectangle is fully covered without any overlap or overflow of the smaller rectangles. What is the minimum possible area of the large rectangle?

你有N个矩形（N> 1）。 这些矩形的短边和长边的长度使用的2N个数都是各不相同的正整数。

你可以使用所有这些矩形创建一个更大的矩形。 大矩形正好被完全覆盖，没有任何小矩形的重叠或溢出。大矩形的最小可能面积是多少？

newkid

我比划了一下，五个矩形可以组成一个13X13，不知道有没有更小的，楼下继续。

〇〇

https://baike.baidu.com/item/%E5 ... /1742595?fr=aladdin

用不同大小面积的正方形填满一个大的正方形

https://en.wikipedia.org/wiki/Squaring_the_square

〇〇

用长方形填充正方形
http://www.ituring.com.cn/article/41369

用正方形填充长方形
https://blog.csdn.net/flyingscv/article/details/1928367

solomon_007

16#

SQL>
SQL>  with t as
  2            (select sys_connect_by_path(n,',') nlist
  3              from (select level n from dual connect by level<=11)
  4             where level = 10
  5            connect by nocycle prior n <> n),
  6      s as (
  7            select regexp_substr(nlist,'[^,]+',1,1)  x1,
  8                   regexp_substr(nlist,'[^,]+',1,2)  y1,
  9                   regexp_substr(nlist,'[^,]+',1,3)  x2,
10                   regexp_substr(nlist,'[^,]+',1,4)  y2,
11                   regexp_substr(nlist,'[^,]+',1,5)  x3,
12                   regexp_substr(nlist,'[^,]+',1,6)  y3,
13                   regexp_substr(nlist,'[^,]+',1,7)  x4,
14                   regexp_substr(nlist,'[^,]+',1,8)  y4,
15                   regexp_substr(nlist,'[^,]+',1,9)  x5,
16                   regexp_substr(nlist,'[^,]+',1,10) y5
17              from t),
18          r as (
19                  select x1,y1,
20                         x2,y2,
21                         x3,y3,
22                         x4,y4,
23                         x5,y5
24                    from s
25                   where x1 = x4 + x5
26                     and x3 = x2 + x5
27                     and y2 = y1 + y5
28                     and y4 = y3 + y5
29                     and y1 + y4 = y2 + y3
30                     and x1 + x2 = x3 + x4)
31  select x1,y1,
32         x2,y2,
33         x3,y3,
34         x4,y4,
35         x5,y5,
36         (x1+x2)||'*'||(y2+y3) as rec_area
37    from r
38   where (x1+x2)*(y2+y3) = (select min((x1+x2)*(y2+y3)) from r)
39  /
X1  Y1  X2  Y2  X3  Y3  X4  Y4  X5  Y5  REC_AREA
--- --- --- --- --- --- --- --- --- --- ----------
6   2   3   9   8   4   1   11  5   7   9*13
6   4   3   11  8   2   1   9   5   7   9*13
8   2   1   9   6   4   3   11  5   7   9*13
8   4   1   11  6   2   3   9   5   7   9*13
9   1   4   6   11  3   2   8   7   5   13*9
9   3   4   8   11  1   2   6   7   5   13*9
11  1   2   6   9   3   4   8   7   5   13*9
11  3   2   8   9   1   4   6   7   5   13*9
8 rows selected       

6*2 + 3*9 + 8*4 + 1*11 + 5*7 = 9*13 = 117
...

所以最小的应该是 9*13

solomon_007

c:\temp\a.png

solomon_007

n = 10 也又值，但面积不是最小

SQL>
SQL>  with t as
  2            (select sys_connect_by_path(n,',') nlist
  3              from (select level n from dual connect by level<=10)
  4             where level = 10
  5            connect by nocycle prior n <> n),
  6      s as (
  7            select regexp_substr(nlist,'[^,]+',1,1)  x1,
  8                   regexp_substr(nlist,'[^,]+',1,2)  y1,
  9                   regexp_substr(nlist,'[^,]+',1,3)  x2,
10                   regexp_substr(nlist,'[^,]+',1,4)  y2,
11                   regexp_substr(nlist,'[^,]+',1,5)  x3,
12                   regexp_substr(nlist,'[^,]+',1,6)  y3,
13                   regexp_substr(nlist,'[^,]+',1,7)  x4,
14                   regexp_substr(nlist,'[^,]+',1,8)  y4,
15                   regexp_substr(nlist,'[^,]+',1,9)  x5,
16                   regexp_substr(nlist,'[^,]+',1,10) y5
17              from t),
18          r as (
19                  select x1,y1,
20                         x2,y2,
21                         x3,y3,
22                         x4,y4,
23                         x5,y5
24                    from s
25                   where x1 = x4 + x5
26                     and x3 = x2 + x5
27                     and y2 = y1 + y5
28                     and y4 = y3 + y5
29                     and y1 + y4 = y2 + y3
30                     and x1 + x2 = x3 + x4)
31  select x1,y1,
32         x2,y2,
33         x3,y3,
34         x4,y4,
35         x5,y5,
36         (x1+x2)||'*'||(y2+y3) as rec_area
37    from r
38   where (x1+x2)*(y2+y3) = (select min((x1+x2)*(y2+y3)) from r)
39  /
X1      Y1      X2      Y2      X3      Y3      X4      Y4      X5      Y5      REC_AREA
------- ------- ------- ------- ------- ------- ------- ------- ------- ------- -------
6       1       5       8       9       3       2       10      4       7       11*11
6       3       5       10      9       1       2       8       4       7       11*11
8       2       3       6       10      5       1       9       7       4       11*11
8       5       3       9       10      2       1       6       7       4       11*11
9       1       2       8       6       3       5       10      4       7       11*11
9       3       2       10      6       1       5       8       4       7       11*11
10      2       1       6       8       5       3       9       7       4       11*11
10      5       1       9       8       2       3       6       7       4       11*11
帮你编辑了
8 rows selected

SQL> select 11*11 from dual;
     11*11
----------
       121

SQL>

〇〇

有没有可能6个矩形更小