随便写写,不一定对,有误请指出。
感觉考虑反向问题「给定的气数下最多能摆多少棋子」会更简单一些。
观察一些简单的结构:
?*?
XXX
在这种结构中,无论 ? 的情况如何,只要 X 处全有子,那么,在 * 处也放子,气的数量不会增加。
X*?
?XX
同上。
所以答案的边界一定:
所以答案一定形如:四个方向上最远的边的长度为 1 或 2,它们之间用 45° 折线连接。
考虑按这四条边的长度对这种图案进行分类,依次为 1111 1122 1212 2222 分别称为 A B C D。
除了 1122 情形外可以证明「对边」长度必然相等,且长宽之间对称。1122 情形规定两个 1 之间的折线段长度为宽 m ,12 之间的折线段长度为长 n 。长宽都是指由多少个 270° 拐弯构成。
那么
气 | 面积 | |
---|---|---|
A(n,m) | 2n+2m+4 | 2nm+n+m+1 |
B(n,m) | 2n+2m+5 | 2nm+n+2m+1 |
C(n,m) | 2n+2m+6 | 2nm+2n+2m+2 |
D(n,m) | 2n+2m+8 | 2nm+3n+3m+4 |
2k 气时可以用 A 或 C 或 D 得到 \lfloor (k-2)^2/2\rfloor +k-1 或 \lfloor (k-3)^2/2\rfloor+2k-4 或 \lfloor (k-4)^2/2\rfloor+3k-8 个子。前者大于等于后两者。写出来就是 \lfloor(k^2-2k+2)/2\rfloor 。
2k+1 气时可以用 B 得到 k(k-1)/2 个子。这比退化的前者要大。
最终可以得到 t 气最多 \lfloor t^2/8-t/2+1\rfloor 子。
反过来写就是 x 子最少 \lceil2+\sqrt{8x-4}\rceil 气。