作者LPH66 (-858993460)
看板puzzle
标题Re: [中译] ProjectEuler 321 Swapping Counters
时间Sun Jan 23 10:03:04 2011
321. Swapping Counters
http://projecteuler.net/index.php?section=problems&id=321
一列有 2n+1 个方格的横排，左边有 n 个红棋子，右边有 n 个蓝棋子，
每个占一格，中间留下一格空格。例如下例是 n = 3 的情形：
┌─┬─┬─┬─┬─┬─┬─┐
│
●│
●│
●│ │
●│
●│
●│
└─┴─┴─┴─┴─┴─┴─┘
每个棋子可以向旁边移动一格或跳过一个棋子停在它後方的空格。
＿
┌─┬─┐ ┌─／─↘─┐
│
●→ │ │
●│
●│ │
└─┴─┘ └─┴─┴─┘
令 M(n) 表示将两边颜色交换所需要的最少步数。
也就是说，把红色移到最右边，蓝色移到最左边。
可以检查 M(3) = 15，正好它也是一个三角形数。
若列出所有 M(n) 正好是三角形数的 n，
则前五项是：1, 3, 10, 22, 63, 其和为 99。
求前四十项的和。
--
动作太慢只抢到第十五名....= =
(这篇文章 PO 出时第十九名已经被抢走了)
噢对了，这个数列 OEIS 并没有收录 (不然就不会是 40 这个数字了...)
--
実琴：「
河野！你真的就这样被
物质慾望给吸引过去了吗?!」
亨：「只要
穿着女装摆出亲切的样子，所有必要花费就能
全免，似乎一点都不坏啊。」
実琴：「难道你没有
男人的尊严了吗?!」
亨：(断然道)「
没有。在
节衣缩食且
生活吃紧的
学生面前，
没有那种东西。」
－－プリンセス・プリンセス 第二话
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.28.92
※ 编辑: LPH66 来自: 140.112.28.92 (01/23 10:03)
※ 编辑: LPH66 来自: 140.112.28.92 (01/23 10:04)
1F：→ LPH66:可恶我笑了XD 竟然另一个相关的数列在 OEIS 上 XDDDDD 01/23 10:27
2F：→ LPH66:糟了还不只一个相关数列在上面 XDDDDDDDDDDD 01/23 10:31
3F：推 babufong:15名也还不错 从床上惊醒时就已经看到19了 01/23 11:11
4F：推 utomaya:用BFS得出M(n)=n*(n+2) 01/23 12:06
5F：→ utomaya:不过要解这方程式n*(n+2)=k*(k+1)/2到第40项 还真有点难度 01/23 12:08
6F：推 weselyong:这游戏我在Ｍａｃｈｉｎａｒｉｕｍ里面玩过！！ 01/23 21:27