# P81: 路径和 - 两个方向
Path sum: two ways
在如下的
\begin{pmatrix} \color{red}{131} & 673 & 234 & 103 & 18\\ \color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & 150\\ 630 & 803 & \color{red}{746} & \color{red}{422} & 111\\ 537 & 699 & 497 & \color{red}{121} & 956\\ 805 & 732 & 524 & \color{red}{37} & \color{red}{331} \end{pmatrix}
在这个 31K 的文本文件 matrix.txt 中包含了一个
和 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 开始的编程语言.
动态规划写出来也和公式一样美观啊
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]];当然其实很多人审美有问题不觉得这个美观....
所以我按另一种审美写了个:
A = Import["https://projecteuler.net/project/resources/p081_matrix.txt", "CSV"];
DP[i_, j_] := DP[i, j] = Which[i > 80$$Or]j > 80$$Or]i < 1$$Or]j < 1, Infinity,
i == 1 && j == 1, A[[1, 1]], True, Min[DP[i - 1, j], DP[i, j - 1]] + A[[i, j]]]
DP@@Dimensions@A# P82: 路径和 - 三个方向
Path sum: three ways
注意: 这是第 81 题的一个更具挑战性的版本.
在如下的 5 × 5 矩阵中, 从最左栏任意一格出发, 始终只向右, 向上或向下移动, 到最右栏任意一格结束的最小路径和为 994, 由标注红色的路径给出.
\begin{pmatrix} 131 & 673 & \color{red}{234} & \color{red}{103} & \color{red}{18}\\ \color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & 150\\ 630 & 803 & 746 & 422 & 111\\ 537 & 699 & 497 & 121 & 956\\ 805 & 732 & 524 & 37 & 331 \end{pmatrix}
在这个 31K 的文本文件 matrix.txt 中包含了一个
我感觉到了套路的味道... 下一道不会要四个方向了吧?
啊哈, 还真是, 我测了下连三个矩阵都是一样的说, 那就是 Dijkstra 了......
不过我为什么要自己撸一个 Dijkstra, 脑子瓦特了, 把他变成图, 剩下的交给 Mathematica...
我们可以直接邻接化这个 80×80 的矩阵变成 6400×6400 的大型稀疏邻接矩阵, 然后 AdjacencyGraph 变成 Graph 对象.... 怎么感觉有点逗比..
不行我得查查高级解决方案.... 唔, 有个古函数 MakeGraph... 不过这是个古函数了, 得找到使用方法....
10 分钟过去了....... 好吧, I'm angry, 我之后得撸个程序包...
SquareMatrix = Import["https://projecteuler.net/project/resources/p082_matrix.txt", "CSV"];
n = Length[SquareMatrix];path[i_, n, _] := A[[i, n]];
path[0, _, _] := Infinity;path[n + 1, _, _] := Infinity;
path[i_, j_, up_] := path[i, j, up] = A[[i, j]] + Min[path[i, j + 1, up], path[i, j + 1, !up], path[i + If[up, -1, 1], j, True]];
Min[Table[path[i, 1, True], {i, 1, n}], Table[path[i, 1, False], {i, 1, n}]]# P83: 路径和 - 四个方向
TIP
注意: 这是第 81 题的一个极具挑战性的版本.
在如下的 5 × 5 矩阵中, 从左上角到右下角任意地向上, 向下, 向左或向右移动的最小路径和为 2297, 由标注红色的路径给出.
\begin{pmatrix} \color{red}{131} & 673 & \color{red}{234} & \color{red}{103} & \color{red}{18}\\ \color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & \color{red}{150}\\ 630 & 803 & 746 & \color{red}{422} & \color{red}{111}\\ 537 & 699 & 497 & \color{red}{121} & 956\\ 805 & 732 & 524 & \color{red}{37} & \color{red}{331} \end{pmatrix}
在这个 31K 的文本文件 matrix.txt 中包含了一个
用 HTML 画表格好捉急啊, HTML 这种玩意儿是给人写的吗....
SquareMatrix = Import["https://projecteuler.net/project/resources/p083_matrix.txt", "CSV"];
n = Length[SquareMatrix];
path[n, n, _] := A[[n, n]];path[i_, j_, 0] := Infinity;
path[0, _, _] := Infinity;path[n + 1, _, _] := Infinity;(* 封住左右墙 *)
path[_, 0, _] := Infinity;path[_, n + 1, _] := Infinity;(* 封住上下墙 *)
path[i_, j_, steps_] := path[i, j, steps] = A[[i, j]] + Min[path[i + 1, j, steps - 1], path[i, j + 1, steps - 1], path[i - 1, j, steps - 1], path[i, j - 1, steps - 1]];
path[1, 1, 200(* 确切的说是 164 步 *)]# P84: 大富翁几率
Monopoly odds
大富翁游戏的标准棋盘大致如下图所示:
玩家从标记有 "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: 数长方形
Counting rectangles
如果数得足够仔细, 能看出在一个
尽管没有一个长方形网格中包含有恰好两百万个长方形, 但有许多长方形网格中包含的长方形数目接近两百万, 求其中最接近这一数目的长方形网格的面积.
我就数得一点都不仔细, 我数了好几遍还没数对. 感觉这种题肯定有生成函数解法.
好吧不用生了, 脑袋转个弯就出来了, 长方形就是长里面选两条, 宽里面选两条, 那就是
这么说顺便也解决掉了高维中的情况了, 然后就解方程呗....
Minimize[{Abs[(n^2+n) (m^2+m)/4-2000000],0<m<100,0<n<100},{m,n},Integers]我还是给点干货吧, 如果是求正方形的话就是小正方形移动呗, 然后高维推广也不难看出, 化简就免了...
\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: 长方体路径
Cuboid route
蜘蛛 S 位于一个 6 × 5 × 3 大小的长方体屋子的一角, 而苍蝇 F 则恰好位于其对角. 沿着屋子的表面, 从 S 到 F 的最短 "直线" 距离是 10, 路径如下图所示:
然而, 对于任意长方体, "最短" 路径实际上一共有三种可能; 而且, 最短路径的长度也并不一定为整数.
当 M=100 时, 若不考虑旋转, 所有长, 宽, 高均不超过 M 且为整数的长方体中, 对角的最短距离是整数的恰好有 2060 个; 这是使得该数目超过两千的最小 M 值; 当 M=99 时, 该数目为 1975.
找出使得该数目超过一百万的最小 M 值.
死算的话有点慢, 我们来分析下:
令
于是我们发现对于给定的 b ⩽ 2k, 解就是
foo[m_]:=Total[Floor[#/2]+1-Max[1,#-m]&/@Select[(#-Reverse[#])/2&[Divisors[m^2]],IntegerQ[#]&&0<#<=2 m&]]
Last@Most@NestWhileList[{#[[1]]+foo[#[[2]]],#[[2]]+1}&,{0,1},#[[1]]<1*^6&]# P87: 素数幂三元组
Prime power triples
最小的可以表示为一个素数的平方, 加上一个素数的立方, 再加上一个素数的四次方的数是 28. 实际上, 在小于 50 的数中, 一共有 4 个数满足这一性质:
28 = 22 + 23 + 24 33 = 32 + 23 + 24 49 = 52 + 23 + 24 47 = 22 + 33 + 24
有多少个小于五千万的数, 可以表示为一个素数的平方, 加上一个素数的立方, 再加上一个素数的四次方?
我靠, 不会是三重循环遍历吧, 有点坑爹啊, 我要骂人了, 这几道题太不友好了....
这种题你和我说有会有数论解法? 数论解法估计是没有的了, 造个筛法应该还是可以的.
当然是从高次开始筛, 减完筛低次, 全都筛完还剩下的就是解了. 该程序已同步到 BGG 包.
PrimePowerTuple[max_,rule_]:=Block[{sifter}, sifter[l_,x_]:=Union@@(#+Array[Prime,PrimePi[(max-#)^(1/x)]]^x&/@l);
Fold[sifter,{0},Sort[rule,Greater]]]
Length@PrimePowerTuple[5*^7,{2,3,4}]# P88: 积和数
Product-sum numbers
若自然数 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, 然而看不太懂他在说啥...
$CharacterEncoding="UTF-8";
Get["https://raw.githubusercontent.com/GalAster/BiGridGenerator/master/BiGridGenerator/Kernel/ExCode/ExNumber.m"];
Information/@{SumProdPartitions,SumProdNumber};
Total@SumProdNumber[12000]# P89: 罗马数字
Roman numerals
要正确地用罗马数字表达一个数, 必须遵循一些基本规则. 尽管符合规则的写法有时会多于一种, 但对每个数来说总是存在一种 "最好的" 写法.
例如, 数 16 就至少有六种写法:
- IIIIIIIIIIIIIIII
- VIIIIIIIIIII
- VVIIIIII
- XIIIIII
- VVVI
- XVI
然而, 根据规则, 只有 XIIIIII 和 XVI 是合理的写法, 而后一种因为使用了最少的数字而被认为是最有效的写法.
在这个 11K 的文本文件 roman.txt 中包含了一千个合理的罗马数字写法, 但并不都是最有效的写法; 有关罗马数字的明确规则, 可以参考关于罗马数字.
求出将这些数都写成最有效的写法所节省的字符数.
注意: 你可以假定文件中的所有罗马数字写法都不包含连续超过四个相同字符.
阅读理解题...
就是说某些模式能化简, 然后找到这个化简规则就行.
in=ReadList["https://projecteuler.net/project/resources/p089_roman.txt",String];
rule={"IIII"->"IV","VIV"->"IX","XXXX"->"XL","LXL"->"XC","CCCC"->"CD","DCD"->"CM"};
Tr@StringLength@#&@in-Tr@StringLength@#&@FixedPoint[#~StringReplace~rule&,in]# P90: 立方体数字对
Cube digit pairs
在一个立方体的六个面上分别标上不同的数字 (从 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 上去看看有没有变化就行了.
DiceQ[dice_]:=Block[{pos=Tuples[DeleteCases[{dice},7,All]],ans},
ans=Union[10#[[1]]+#[[2]]&/@pos];Union[ans,Range[9]^2]==ans]
Tr@Boole[DiceQ@@@Subsets[Subsets[{0,1,2,3,4,5,6,7,8,6},{6}],{2}]]不知为何这道题做出来的人不多, 难度显示说有 40%......
连续计时, 1 小时 46 分钟 11 秒.... 要命, 都是硬计算....
你知道吗, 我做到 30 题的时候感觉 2 小时能杀光 100 题是绰绰有余的...
然后就不断被各种题各种焦作人了.....
主要是查资料查起来没时间感.....
有这个查的时间自己撸代码也能撸出来了.....