puzzleup 2020 11月开始

solomon_007

newkid 发表于 2020-11-30 22:14
给猫猫转了章。我的写法：没有必要每条路径都走到底，这样会快一些。WITH t(box1,box2,lvl) AS (SELECT 10, ...

  没有必要每条路径都走到底，对的。每个 （5，0）或（0，5）的叶子节点的概率都是
1/2^15

dhhb

我觉得还是不对，分母如果是2^15，意味吃15次，而题意是一盒吃完后另一盒剩5个的概率，也就是说另一盒可能剩一个，这样就是吃19次，所以15没有包含全部的样板空间。

newkid

dhhb 发表于 2020-11-30 22:39
我觉得还是不对，分母如果是2^15，意味吃15次，而题意是一盒吃完后另一盒剩5个的概率，也就是说另一盒可能 ...

你说的19次结束游戏的其实被我的分母包含了，但不是这个叶子本身，而是它的祖先的一个高度15的枝条节点。
19次当然是一个有效的结果，但是，它的概率比15次要小，就是我说的，藏得比较深的迷宫出口。你把全部叶子都加上，其实就意味着把它们的权重都看作相等的，这是不对的。
以(2,2)为简单例子：
初始：(2,2)
第一颗：(1,2)  ---- 1/2
        (2,1)  ---- 1/2
第二颗：(0,2)  ---- 1/4 (叶子)
        (1,1)  ---- 1/4
        (2,0)  ---- 1/4 (叶子)
        (1,1)  ---- 1/4
第三颗：(0,1)  ---- 1/8 (叶子)
        (1,0)  ---- 1/8 (叶子)
        (0,1)  ---- 1/8 (叶子)
        (1,0)  ---- 1/8 (叶子)

这种情况下，一盒为空另一盒2颗的概率是1/4+1/4=1/2
而不是 2/6

newkid

#5 LAST TWO GOALS

Your football team won a match with the score of 5-4. What is the probability that your team has scored the last two goals?

Enter your answer as a simplified fraction. Example:12/23

你的足球队以5-4的比分赢得了一场比赛。最后两个进球来自你的球队的概率是多少？

将你的答案以简化分数输入。例：12/23

---这个和上一题很像，但它不是求某种状态的概率，而是求到达特定状态的某些特定路径的概率。

solomon_007

# 5

SQL> with t as (select level n,case when level <= 5 then 'A' else 'B' end ball from dual connect by level<=9),
  2       s(lvl,ball_path,n_path) as (select 1,ball,cast(n as varchar2(100)) from t
  3                             union all
  4                            select lvl+1,
  5                                   s.ball_path||t.ball,
  6                                   s.n_path||t.n
  7                             from s,t
  8                            where lvl < 9
  9                              and instr(s.n_path,t.n)=0),
10       r as (select count(*) total_cnt,
11                    count(case when substr(ball_path,9-2,2)='AA' then 1 end) cnt
12               from ( select distinct ball_path from s where lvl = 9 )
13             ),
14      f(total_cnt,cnt) as (select total_cnt,cnt from r
15                        union all
16                       select greatest(total_cnt - cnt,cnt),least(total_cnt - cnt,cnt)
17                         from f
18                       where total_cnt <> cnt)
19   select r.cnt/f.cnt||'/'||r.total_cnt/f.cnt as res
20     from r,f
21    where f.total_cnt = f.cnt
22  /

RES
--------------------------------------------------------------------------------
5/18

这个概率题要简单多了。

newkid

已发章。

我的写法：
WITH t(s1,s2,path) AS (
SELECT 0,0,cast('' as varchar2(10)) FROM DUAL
UNION ALL
SELECT DECODE(n,1,s1+1,s1)
      ,DECODE(n,2,s2+1,s2)
      ,path||n
  FROM t,(SELECT 1 n FROM DUAL UNION ALL SELECT 2  FROM DUAL)
WHERE s1<=5 and s2<=4
)
select count(*) cnt
      ,count(case when substr(path,-2)='11' then 1 end)
from t where s1=5 and s2=4;

126 35

手算：

4个进球分布到5个进球之中(6个位置可放)，把4个分组：              
1组：C(6,1) = 6
2组：13,22,31 三种，C(6,2)*3 = 45
3组：112,121,211 共3种，C(6,3)*3 = 60
4组：1111 一种，C(6,4)*1 = 15

共126

最后两个进球固定，4个进球分布到3个进球之中(4个位置可放)，把4个分组：              
1组：C(4,1) = 4
2组：13,22,31 三种，C(4,2)*3 = 18
3组：112,121,211 共3种，C(4,3)*3 = 12
4组：1111 一种，C(4,4)*1 = 1

共35

newkid

#6 TWO SQUARES

There is a 6 by 6 dotty grid. You will draw two squares by joining the dots.

In how many ways can this drawing be accomplished?

-The squares cannot have common dots or areas.
-Rotations or reflections of a drawing are considered distinct.

The figure above demonstrates two possible drawings.


有一个6乘6的点状网格。你将通过连接点画出两个正方形。

有多少种方法可以完成这种画法？

正方形不能有共同的点或区域。
一种画法的旋转或翻转被认为是不同的。

上图展示了两种可能的画法。

newkid

第一步，先构造出所有正方形，我弄出105个，有没人来对一下答案。

剩下的工作是找一个算法判断一个点是否在矩形之内，网上可以搜到。

jihuyao

Let me throw a brick.  Each square can be identified by its rid, cid, and length.  If all are ordered by rid, cid, length with sequence number rn, the self-join with rn(i)<rn(j) will give all possible combinations of any two squares in the generated square list.  Then I would think there is formula based on the location of each square (top left corner) by rid, cid, and its length to check if the two combined squares have any shared points (including points in shared lines or area).

〇〇

没有看到图