欧拉挑战:入门8段

Aster 欧拉挑战 Leave a Comment

P81:路径和:两个方向

在如下的5乘5矩阵中,从左上方到右下方始终只向右或向下移动的最小路径和为2427,由标注红色的路径给出。

13167323410318
20196342965150
630803746422111
537699497121956
80573252437331

在这个31K的文本文件matrix.txt(右击并选择“目标另存为……”)中包含了一个80乘80的矩阵,求出从该矩阵的左上方到右下方始终只向右和向下移动的最小路径和。

和67题一样,不过我那个算法只是定义给三角形的...

虽然正方形就是两个三角形叠起来,不过倒来倒去不麻烦嘛...

有的这么折腾还不如写个正统的动态规划.

$$\begin{aligned}
B[1,1] &= A[1,1]\\
B[i,j] &= B[i,j - 1] + A[i,j]\quad &if\;i = 1\\
&= B[i - 1,j] + A[i,j]\quad &if\;j = 1\\
&= \min (B[i - 1,j],B[i,j - 1]) + A[i,j]\\
\end{aligned}$$

然后直接公式翻译成代码就行了,注意Mathematica是少数和人类习惯一样下标从1开始的编程语言.

这倒不是MMA人性化或者傲娇.MMA的下标其实也是从0开始的,但是下标0分配给了类型,也就是表头.

动态规划写出来也和公式一样美观啊

B[1, 1] := A[[1, 1]];
B[1, j_] := B[1, j - 1] + A[[1, j]];
B[i_, 1] := B[i - 1, 1] + A[[i, 1]];
B[i_, j_] := B[i, j] = Min[B[i - 1, j], B[i, j - 1]] + A[[i, j]];

当然其实很多人觉得这个很丑来着你们说美观的是什么心态....所以我按另一种审美写了个:


P82:路径和:三个方向

注意:这是第81题的一个更具挑战性的版本。

在如下的5乘5矩阵中,从最左栏任意一格出发,始终只向右、向上或向下移动,到最右栏任意一格结束的最小路径和为994,由标注红色的路径给出。

13167323410318
20196342965150
630803746422111
537699497121956
80573252437331

在这个31K的文本文件matrix.txt(右击并选择“目标另存为……”)中包含了一个80乘80的矩阵,求出从最左栏到最右栏的最小路径和。

我感觉到了套路的味道...下一道不会要四个方向了吧?

啊哈,还真是,我测了下连三个矩阵都是一样的说,那就是Dijkstra了......

不过我为什么要自己撸一个Dijkstra,脑子瓦特了,把他变成图,剩下的交给Mathematica...

我们可以直接邻接化这个80×80的矩阵变成6400×6400的大型稀疏邻接矩阵,然后AdjacencyGraph变成Graph对象....怎么感觉有点逗比..

不行我得查查高级解决方案....唔,有个古函数MakeGraph...不过这是个古函数了得找到激活方法....

10分钟过去了.......好吧,I'm angry,我之后得撸个程序包...


P83:路径和:四个方向

注意:这是第81题的一个极具挑战性的版本。

在如下的5乘5矩阵中,从左上角到右下角任意地向上、向下、向左或向右移动的最小路径和为2297,由标注红色的路径给出。

13167323410318
20196342965150
630803746422111
537699497121956
80573252437331

在这个31K的文本文件matrix.txt(右击并选择“目标另存为……”)中包含了一个80乘80的矩阵,求出从左上角到右下角任意地向上、向下、向左或向右移动的最小路径和。

用HTML画表格好捉急啊...

HTML这种玩意儿是给人写的吗....


P84:大富翁几率

大富翁游戏的标准棋盘大致如下图所示:

GOA1CC1A2T1R1B1CH1B2B3JAIL
H2C1
T2U1
H1C2
CH3C3
R4R2
G3D1
CC3CC2
G2D2
G1D3
G2JF3U2F2F1R3E3E2CH2E1FP

玩家从标记有“GO”的方格出发,掷两个六面的骰子并将点数和相加,作为本轮他们前进的步数。如果没有其它规则,那么落在每一格上的概率应该是2.5%。但是,由于“G2J”(入狱)、“CC”(宝箱卡)和“CH”(机会卡)的存在,这个分布会有所改变。

除了落在“G2J”上,或者在“CC”或“CH”上抽到入狱卡之外,如果玩家连续三次都掷出两个相同的点数,则在第三次时将会直接入狱。

游戏开始时,“CC”和“CH”所需的卡片将被洗牌打乱。当一个玩家落在“CC”或“CH”上时,他们从宝箱卡和机会卡的牌堆最上方取一张卡并遵循指令行事,并将该卡再放回牌堆的最下方。宝箱卡和机会卡都各有16张,但我们只关心会影响到移动的卡片,其它的卡片我们都将无视它们的效果。

  • 宝箱卡 (2/16 张卡):
    • 回到起点“GO”
    • 进入监狱“JAIL”
  • 机会卡 (10/16 张卡):
    • 回到起点“GO”
    • 进入监狱“JAIL”
    • 移动到“C1”
    • 移动到“E3”
    • 移动到“H2”
    • 移动到“R1”
    • 移动到下一个“R”(铁路公司)
    • 移动到下一个“R”
    • 移动到下一个“U”(公共服务公司)
    • 后退三步

这道题主要考察掷出骰子后停在某个特定方格上的概率。显然,除了停在“G2J”上的可能性为0之外,停在“CH”格的可能性最小,因为有5/8的情况下玩家会移动到另一格。我们不区分是被送进监狱还是恰好落在监狱“JAIL”这一格,而且不考虑需要掷出两个相同的点数才能出狱的要求,而是假定进入监狱的第二轮就会自动出狱。

从起点“GO”出发,并将方格依次标记00到39,我们可以将这些两位数连接起来表示方格的序列。

统计学上来说,三个最有可能停下的方格分别是“JAIL”(6.24%)或方格10,E3(3.18%)或方格24以及“GO”(3.09%)或方格00。这三个方格可以用一个六位数字串表示:102400。

如果我们不用两个六面的骰子而是用两个四面的骰子,求出三个最有可能停下的方格构成的数字串。

按惯例跳过,未计时.

这道题一点意思都没有,就是蒙特卡洛...

没有监狱的话还好,是个马尔科夫过程,加入了入狱出狱的设定就瞬间炸了,没有数学模型能解了...


P85:数长方形

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

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

我就数得一点都不仔细,我数了好几遍还没数对.感觉这种题肯定有生成函数解法.

好吧不用生了,脑袋转个弯就出来了,长方形就是长里面选两条,宽里面选两条,那就是

$$S(i,j) = C_i^2C_j^2 = \frac{1}{4}({i^2} + i)({j^2} + j)$$

这么说顺便也解决掉了高维中的情况了,然后就解方程呗....

我还是给点干货吧,如果是求正方形的话就是小正方形移动呗,然后高维推广也不难看出,化简就免了...

$$\begin{aligned}
d &= \min (m,n)\\
S&=\sum\limits_{a = 1}^{d - 1} {(m - a)} (n - a)\\
&= \frac{1}{6}(d - 1)(2{d^2} - d(3m + 3n + 1) + 6mn)\\
&= \frac{1}{6}(d - 1)(3mn - d(d + 1))
\end{aligned}$$


P86:长方体路径

蜘蛛S位于一个6乘5乘3大小的长方体屋子的一角,而苍蝇F则恰好位于其对角。沿着屋子的表面,从S到F的最短“直线”距离是10,路径如下图所示:

然而,对于任意长方体,“最短”路径实际上一共有三种可能;而且,最短路径的长度也并不一定为整数。

当M=100时,若不考虑旋转,所有长、宽、高均不超过M且为整数的长方体中,对角的最短距离是整数的恰好有2060个;这是使得该数目超过两千的最小M值;当M=99时,该数目为1975。

找出使得该数目超过一百万的最小M值。

死算的话有点慢,我们来分析下:

令${F(k)}$是当最大长度为k的长方体中解的数目,所以我们要求的就是第一个使得$\sum\limits_{1 \leqslant k \leqslant n} {F(k)}$超过百万的n值减1. 其他两条边与k构成勾股三元组 .因此对于固定的b,每一种b能被写成两个小于k的正整数之和的方式代表另一个解.

于是我们发现对于给定的b ≤ 2k,解就是$\left\lfloor {\frac{b}{2}} \right\rfloor  + 1 - Max(1,k - b)$,值为0代表无解. 然后加起来就是固定$k$下的解数目了.


P87:素数幂三元组

最小的可以表示为一个素数的平方,加上一个素数的立方,再加上一个素数的四次方的数是28。实际上,在小于50的数中,一共有4个数满足这一性质:

28 = 22 + 23 + 24
33 = 32 + 23 + 24
49 = 52 + 23 + 24
47 = 22 + 33 + 24

有多少个小于五千万的数,可以表示为一个素数的平方,加上一个素数的立方,再加上一个素数的四次方?

我靠,不会是三重循环遍历吧,有点坑爹啊,我要骂人了,这几道题太不友好了....

这种题你和我说有会有数论解法?数论解法估计是没有的了,造个筛法应该还是可以的.

当然是从高次开始筛,减完筛低次,全都筛完还剩下的就是解了.该程序已同步到BGG包.


P88:积和数

若自然数N能够同时表示成一组至少两个自然数{a1, a2, … , ak}的积和和,也即N = a1 + a2 + … + ak = a1 × a2 × … × ak,则N被称为积和数。

例如,6是积和数,因为6 = 1 + 2 + 3 = 1 × 2 × 3。

给定集合的规模k,我们称满足上述性质的最小N值为最小积和数。当k = 2、3、4、5、6时,最小积和数如下所示:

k=2: 4 = 2 × 2 = 2 + 2
k=3: 6 = 1 × 2 × 3 = 1 + 2 + 3
k=4: 8 = 1 × 1 × 2 × 4 = 1 + 1 + 2 + 4
k=5: 8 = 1 × 1 × 2 × 2 × 2 = 1 + 1 + 2 + 2 + 2
k=6: 12 = 1 × 1 × 1 × 1 × 2 × 6 = 1 + 1 + 1 + 1 + 2 + 6

因此,对于2≤k≤6,所有的最小积和数的和为4+6+8+12 = 30;注意8只被计算了一次。

已知对于2≤k≤12,所有最小积和数构成的集合是{4, 6, 8, 12, 15, 16},这些数的和是61。

对于2≤k≤12000,所有最小积和数的和是多少?

可能性太多了,写不出跑进1 min的算法...放弃

不过我当时搜索到了一篇论文Arixv,然而看不太懂他在说啥...


P89:罗马数字

要正确地用罗马数字表达一个数,必须遵循一些基本规则。尽管符合规则的写法有时会多于一种,但对每个数来说总是存在一种“最好的”写法。

例如,数16就至少有六种写法:

IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI

然而,根据规则,只有XIIIIII和XVI是合理的写法,而后一种因为使用了最少的数字而被认为是最有效的写法。

在这个11K的文本文件roman.txt (右击并选择“目标另存为……”)中包含了一千个合理的罗马数字写法,但并不都是最有效的写法;有关罗马数字的明确规则,可以参考关于罗马数字

求出将这些数都写成最有效的写法所节省的字符数。

注意:你可以假定文件中的所有罗马数字写法都不包含连续超过四个相同字符。

阅读理解题...解略


P90:立方体数字对

在一个立方体的六个面上分别标上不同的数字(从0到9),对另一个立方体也如法炮制。将这两个立方体按不同的方向并排摆放,我们可以得到各种各样的两位数。

例如,平方数64可以通过这样摆放获得:

事实上,通过仔细地选择两个立方体上的数字,我们可以摆放出所有小于100的平方数:01、04、09、16、25、36、49、64和81。

例如,其中一种方式就是在一个立方体上标上{0, 5, 6, 7, 8, 9},在另一个立方体上标上{1, 2, 3, 4, 8, 9}。

在这个问题中,我们允许将标有6或9的面颠倒过来互相表示,只有这样,如{0, 5, 6, 7, 8, 9}和{1, 2, 3, 4, 6, 7}这样本来无法表示09的标法,才能够摆放出全部九个平方数。

在考虑什么是不同的标法时,我们关注的是立方体上有哪些数字,而不关心它们的顺序。

{1, 2, 3, 4, 5, 6}等价于{3, 6, 4, 1, 2, 5}
{1, 2, 3, 4, 5, 6}不同于{1, 2, 3, 4, 5, 9}

但因为我们允许在摆放两位数时将6和9颠倒过来互相表示,这个例子中的两个不同的集合都可以代表拓展集{1, 2, 3, 4, 5, 6, 9}。

对这两个立方体有多少中不同的标法可以摆放出所有的平方数?

允许6 9 相互表示....好好的一个组合问题,这样岂不是把问题复杂化了...

嗯?不对,其实没区别,Subsets[{0, 1, 2, 3, 4, 5, 6, 7, 8, 6}, {6}]就行了.

然后把这些组合分配给俩骰子,C(C(10, 6), 2) = 21945种,穷举不虚的...

然后就是要造一个函数判定一个俩序列是否可以组成平方数.

怎么判定呢....继续穷举好了,穷举所有能构成的数字,看看最后能否包括所有的平方数.

那计算量再乘以6×6那就是790 020,连百万都没有我就放心穷举了.

不过还是可以做点小优化的,比如先删掉所有的7,MemberQ 9次太笨了,直接Union上去看看有没有变化就行了.

不知为何这道题做出来的人不多,难度显示说有40%......


连续计时,1小时46分钟11秒....要命,都是硬计算....

你知道吗,我做到30题的时候感觉2小时能杀光100题是绰绰有余的...然后就不断被各种题各种焦作人了.....

主要是查资料查起来没时间感.....有这个查的时间自己撸代码也能撸出来了....."

发表评论