puzzleup 2016

〇〇

下图中有几个五边形?小学奥数题?
PENTAGONS

How many pentagons are there in the figure below?



If the problem was asked for the figure below the answer would be 9.

[ You can answer this problem starting from Thursday at 11:00 (GMT) ]

如果是上图,答案是9

newkid

用SQL应该可以，把所有点及其能够通过一条直线到达的点都列出来然后自连接五次。

〇〇

newkid 发表于 2016-10-19 23:31
用SQL应该可以，把所有点及其能够通过一条直线到达的点都列出来然后自连接五次。

连了个4边形
with t as(
select 1 p, 1 l, 2 r, 1 m from dual union
select 2  , 2  , 1  , 1 from dual union
select 3  , 1  , 3  , 2 from dual union
select 4  , 2  , 2  , 2 from dual union
select 5  , 3  , 1  , 2 from dual union
select 6  , 1  ,null, 3 from dual union
select 7  , 2  , 3  , 3 from dual union
select 8  , 3  , 2  , 3 from dual union
select 9  ,null, 1  , 3 from dual),
p(lv,path,l1,r1,m1)as
(
select 1,p,l,r,m from t
union all
select lv+1,path*10+p,l,r,m from t,p
where lv<5 and
(l1=l or r1=r or m1=m)
and (
(instr(path,p)=0 and lv<4)
or
  (instr(path,p)=1 and lv=4)
))
select min(path) from p where lv=5
group by power(2,substr(path,1,1))+
power(2,substr(path,2,1))+
power(2,substr(path,3,1))+
power(2,substr(path,4,1))
;

〇〇

每次连下一个点必须不在一直线没找到简单写法

〇〇

〇〇 发表于 2016-10-20 09:03
每次连下一个点必须不在一直线没找到简单写法

加了方向d判断,还不够,出现很多135241的2个只有顶点连着的3角形
with t as(
select 1 p, 1 l, 2 r, 1 m from dual union
select 2  , 2  , 1  , 1 from dual union
select 3  , 1  , 3  , 2 from dual union
select 4  , 2  , 2  , 2 from dual union
select 5  , 3  , 1  , 2 from dual union
select 6  , 1  ,null, 3 from dual union
select 7  , 2  , 3  , 3 from dual union
select 8  , 3  , 2  , 3 from dual union
select 9  ,null, 1  , 3 from dual),
p(lv,path,l1,r1,m1,d)as
(
select 1,p,l,r,m,0 from t
union all
select lv+1,path*10+p,l,r,m,case when l1=l then 1 when r1=r then 2 when m1=m then 3 end from t,p
where lv<6 and d<> case when l1=l then 1 when r1=r then 2 when m1=m then 3 end
(l1=l or r1=r or m1=m)
and (
(instr(path,p)=0 and lv<5)
or
  (instr(path,p)=1 and lv=5)
))
--select count(*) from(
select min(path) from p where lv=6
group by power(2,substr(path,1,1))+
power(2,substr(path,2,1))+
power(2,substr(path,3,1))+
power(2,substr(path,4,1))+
power(2,substr(path,5,1))
;
);

〇〇

想到一个办法，求出2点中间的点存入排除列表
比如 1 8排除4
6 9排除7 8

〇〇

with t as(
select 1 p, 1 l, 2 r, 1 m from dual union
select 2  , 2  , 1  , 1 from dual union
select 3  , 1  , 3  , 2 from dual union
select 4  , 2  , 2  , 2 from dual union
select 5  , 3  , 1  , 2 from dual union
select 6  , 1  ,null, 3 from dual union
select 7  , 2  , 3  , 3 from dual union
select 8  , 3  , 2  , 3 from dual union
select 9  ,null, 1  , 3 from dual),
ex as(
select 1 a,6 b, 3 x from dual union
select 1 a,8 b, 4 x from dual union
select 2 a,7 b, 4 x from dual union
select 2 a,9 b, 5 x from dual union
select 3 a,5 b, 4 x from dual union
select 6 a,8 b, 7 x from dual union
select 6 a,9 b, 7 x from dual union
select 6 a,9 b, 8 x from dual union
select 7 a,9 b, 8 x from dual),
p(lv,path,l1,r1,m1,d)as
(
select 1,p,l,r,m,0 from t
union all
select lv+1,path*10+p,l,r,m,case when l1=l then 1 when r1=r then 2 when m1=m then 3 end from t,p
where lv<6 and d<> case when l1=l then 1 when r1=r then 2 when m1=m then 3 end and
(l1=l or r1=r or m1=m)
and (
(instr(path,p)=0 and lv<5)
or
  (instr(path,p)=1 and lv=5)
)
and not exists(select 1 from ex where ex.x=p and instr(path,a*10+b)>0 or instr(path,b*10+a)>0)
)
--select count(*) from(
select min(path) from p where lv=6
group by power(2,substr(path,1,1))+
power(2,substr(path,2,1))+
power(2,substr(path,3,1))+
power(2,substr(path,4,1))+
power(2,substr(path,5,1))
;
还是漏掉了124581这种情况

〇〇

with t as(
select 1 p, 1 l, 2 r, 1 m from dual union
select 2  , 2  , 1  , 1 from dual union
select 3  , 1  , 3  , 2 from dual union
select 4  , 2  , 2  , 2 from dual union
select 5  , 3  , 1  , 2 from dual union
select 6  , 1  ,null, 3 from dual union
select 7  , 2  , 3  , 3 from dual union
select 8  , 3  , 2  , 3 from dual union
select 9  ,null, 1  , 3 from dual),
ex as(
select 1 a,6 b, 3 x from dual union
select 1 a,8 b, 4 x from dual union
select 2 a,7 b, 4 x from dual union
select 2 a,9 b, 5 x from dual union
select 3 a,5 b, 4 x from dual union
select 6 a,8 b, 7 x from dual union
select 6 a,9 b, 7 x from dual union
select 6 a,9 b, 8 x from dual union
select 7 a,9 b, 8 x from dual),
p(lv,path,l1,r1,m1,d)as
(
select 1,p,l,r,m,0 from t
union all
select lv+1,path*10+p,l,r,m,case when l1=l then 1 when r1=r then 2 when m1=m then 3 end from t,p
where lv<6 and d<> case when l1=l then 1 when r1=r then 2 when m1=m then 3 end and
(l1=l or r1=r or m1=m)
and (
(instr(path,p)=0 and lv<5)
or
  (instr(path,p)=1 and lv=5)
)
and not exists(select 1 from ex where ex.x=p and (instr(path,a*10+b)>0 or instr(path,b*10+a)>0))
)
--select count(*) from(
select min(path) from p where lv=6 and
not exists(select 1 from ex where (substr(path,-2)=a*10+b or substr(path,-2)=b*10+a) and instr(path,ex.x)>0)
group by power(2,substr(path,1,1))+
power(2,substr(path,2,1))+
power(2,substr(path,3,1))+
power(2,substr(path,4,1))+
power(2,substr(path,5,1))
;
还是漏掉135981这种交叉

〇〇

改用2进制表示已经经过的点,where条件写了就取不出值，放在/** **/位置就会数字溢出
/*and bitand(pe,se)=0*/

with t as(
select 1 p,power(2,1)e, 1 l, 2 r, 1 m from dual union
select 2  ,power(2,2) , 2  , 1  , 1 from dual union
select 3  ,power(2,3) , 1  , 3  , 2 from dual union
select 4  ,power(2,4) , 2  , 2  , 2 from dual union
select 5  ,power(2,5) , 3  , 1  , 2 from dual union
select 6  ,power(2,6) , 1  ,null, 3 from dual union
select 7  ,power(2,7) , 2  , 3  , 3 from dual union
select 8  ,power(2,8) , 3  , 2  , 3 from dual union
select 9  ,power(2,9) ,null, 1  , 3 from dual),
ex as(
select 1 a,6 b, 3 x from dual union
select 1 a,8 b, 4 x from dual union
select 2 a,7 b, 4 x from dual union
select 2 a,9 b, 5 x from dual union
select 3 a,5 b, 4 x from dual union
select 6 a,8 b, 7 x from dual union
select 6 a,9 b, 7 x from dual union
select 6 a,9 b, 8 x from dual union
select 7 a,9 b, 8 x from dual),
x as(select a,b,sum(power(2,x))se from ex group by a,b), --se中间包含的点的2进制和
p(lv,path,l1,r1,m1,pe)as
(
select 1,p,l,r,m,e from t
union all
select lv+1,path*10+p,l,r,m,pe+e+nvl(se,0) from p inner join t on(
lv<6 and bitand(e,pe)=0 and
(l1=l or r1=r or m1=m)
and (
(instr(path,p)=0 and lv<5)
or
(instr(path,p)=1 and lv=5)
))
left join x on(substr(path,-1)||p in (a*10+b,b*10+a) /** **/)
----where bitand(pe,se)=0
)
select min(path) from p where lv=6
group by pe-power(2,substr(path,-1))
;

newkid

最后结论是什么？等我有空也来写一个。lugi看来是对今年的题很失望，都没法显示出他的实力。