Euler Project 挨个做- 之三 (Q79-?)

〇〇

这样更好
with t as(select level-1 l from dual connect by level<=10),
t1(a,p,lv) as(select l,power(2,l),1 from t
union all
select l,p+power(2,l),lv+1 from t1,t where a<l and lv<6),
a as(select p ,decode (bitand(p,64+512),64,p+512,512,p+64,p)pa from t1 where lv=6), --p actual ,pa expand
b as(select p,pa pb from a),
s as(select power(2,floor(level*level/10))s1,
power(2,mod(level*level,10))s2 from dual connect by level<=9),
j as(select pa,pb from a,b where pa<pb and not exists(select 1 from s where bitand(pa,s1)*bitand(pb,s2) =0
and bitand(pa,s2)*bitand(pb,s1)=0))
select count(*) from (
select pa,pb from j
);

〇〇

数长方形

如果数得足够仔细，能看出在一个3乘2的长方形网格中包含有18个不同大小的长方形，如下图所示：

如图 enter image description here
尽管没有一个长方形网格中包含有恰好两百万个长方形，但有许多长方形网格中包含的长方形数目接近两百万，求其中最接近这一数目的长方形网格的面积。

思路
以图中长方形为例,有4条竖线,3条横线,其中两对横线和两对竖线能组成1个长方形，横线间的差就是长方形的高度，竖线之差就是宽度。用SQL表示如下：
with x as(select level x from dual connect by level<=4),
y as(select level y from dual connect by level<=3)
select (x2.x-x1.x)width,(y2.y-y1.y)hight,count(*)
from x x1,x x2,y y1,y y2
where x2.x>x1.x and y2.y>y1.y
group by (x2.x-x1.x),(y2.y-y1.y)
order by 1,2;

WIDTH      HIGHT   COUNT(*)
----- ---------- ----------
    1          1          6
    1          2          3
    2          1          4
    2          2          2
    3          1          2
    3          2          1
分析
1x1 : (4-1)(3-1) =6
1x2 : (4-1)(3-2) =3

2x1 : (4-2)(3-1) =4
2x2 : (4-2)(3-2) =2

3x1 : (4-3)(3-1) =2
3x2 : (4-3)(3-2) =1

=(4-1)(3*2-sum(1->2))
+(4-2)(3*2-sum(1->2))
+(4-3)(3*2-sum(1->2))


=(4*3-sum(1->3))(3*2-sum(1->2))
=(12-6)*(6-3)
=18
把4 和 3 用m 和 n代替

可以推测:
对于m*n的长方形，和为
(m*(m-1)-(1+m-1)*(m-1)/2))
*(n*(n-1)-(1+n-1)*(n-1)/2))
=m(m-1)n(n-1)/4
如果把直线根数改成长方形的宽度和高度 则
和=m(m+1)n(n+1)/4
设m是宽度和高度中较大者
则和必<=(m(m+1)/2)^2且>=(n(n+1)/2)^2
面积=mn，和最接近20000，实际就是求mn的最小值

解不等式m*m+m-2sqrt(2000000)>=0，
m>=方程m*m+m-2sqrt(2000000)=0的较大的根 1/2(-1+sqrt((1+4*2000sqrt(2))
SQL> select 1/2*(-1+sqrt(1+4*2000*sqrt(2)))a from dual;

         A
----------
52.6853093
所以m最小值是53，n最大值是53
with m as(select level+52 m from dual connect by level<=100),
n as(select level n from dual connect by level<=53)
select min(m*(m+1)*n*(n+1)/4-2e6) a from m,n where abs(m*(m+1)*n*(n+1)/4-2e6)<=1000;

     A
------
    -2


with m as(select level+52 m from dual connect by level<=100),
n as(select level n from dual connect by level<=53),
min_diff as(select min(m*(m+1)*n*(n+1)/4-2e6) a from m,n where abs(m*(m+1)*n*(n+1)/4-2e6)<=1000)
select m,n,m*n from m,n where m*(m+1)*n*(n+1)/4-2e6=(select a from min_diff);

     M          N        M*N
------ ---------- ----------
    77         36       2772
有些不完美的地方，不知道怎么证明-2是最接近的。

〇〇

〇〇 发表于 2016-11-30 20:21
数长方形

如果数得足够仔细，能看出在一个3乘2的长方形网格中包含有18个不同大小的长方形，如下图所示： ...

这是85题

〇〇

就从1、-1开始测试
with m as(select level+52 m from dual connect by level<=100),
n as(select level n from dual connect by level<=53),
min_diff as(select min(m*(m+1)*n*(n+1)/4-2e6) a from m,n where abs(m*(m+1)*n*(n+1)/4-2e6)<=1000)
select m,n,m*n from m,n where m*(m+1)*n*(n+1)/4-2e6 in (1,-1,2, -2)
;

    M          N        M*N
----- ---------- ----------
   77         36       2772

newkid

25楼，我没用二进制：

WITH s AS (
SELECT str
      ,CASE WHEN INSTR(str,'6')>0 AND INSTR(str,'9')=0 THEN str||'9'
            WHEN INSTR(str,'6')=0 AND INSTR(str,'9')>0 THEN str||'6'
            ELSE str
       END str2
  FROM (SELECT SYS_CONNECT_BY_PATH(c,',') str
         FROM (SELECT LEVEL-1 c FROM DUAL CONNECT BY LEVEL<=10)
        WHERE LEVEL=6
       CONNECT BY NOCYCLE PRIOR c<c
       )
)
,p AS (SELECT TRUNC(LEVEL*LEVEL/10) c1, MOD(LEVEL*LEVEL,10) c2 FROM DUAL CONNECT BY LEVEL<10)
SELECT COUNT(*)
  FROM s s1,s s2
WHERE s1.str<s2.str
       AND NOT EXISTS (SELECT 1 FROM p WHERE NOT (INSTR(s1.str2,p.c1)>0 AND INSTR(s2.str2,p.c2)>0
                                                  OR INSTR(s2.str2,p.c1)>0 AND INSTR(s1.str2,p.c2)>0
                                                 )
                      );

  COUNT(*)
----------
      1217

〇〇

newkid 发表于 2016-11-30 23:05
25楼，我没用二进制：

WITH s AS (

instr的效率也很好