# 平方和球柱：分层构造与按列输出

## 最大数量的证明

记 $C(n)=\lfloor(n+1)^2/2\rfloor-1$ .

**上界。** 设已经放入了 $T=C(n)+1=\lfloor(n+1)^2/2\rfloor$ 个球。考察最大的 $n+1$ 个编号，即 $T-n,\ldots,T$ .其中任意两个不同编号之和严格大于 $n^2$ 且严格小于 $(n+1)^2$ ，所以不能相邻。每根柱子的编号从底到顶严格递增，这些大编号在该柱上必然构成连续的顶端部分；若某柱有两个，就会有两个相邻的大编号，产生矛盾。因此需要至少 $n+1$ 根柱子，上界成立。

**达到上界的构造。** 一根柱子只放球一。对于奇数 $n>1$ ，在当前 $n$ 根柱子上放两层，从顶到底描述如下，局部列编号为 $j=0,\ldots,n-1$ ：

$$\text{上层}_j=C(n)-n+1+j,\qquad \text{下层}_j=C(n)-n-j.$$

再在中间 $n-2$ 根柱子的下方递归放入规模 $n-2$ 的方案。上下两层相邻和为 $n^2$ ；第二层与递归部分第一层的相邻和为 $(n-1)^2$ .剩余相邻关系由归纳保证。两层使用最大的 $2n$ 个编号，因为 $C(n)-C(n-2)=2n$ ，所有编号不重不漏。

对于偶数 $n$ ，最上层从左到右为 $C(n),C(n)-1,\ldots,C(n)-n+1$ ，前 $n-1$ 根柱子的下方放规模 $n-1$ 的方案。相接两层的编号和为 $n^2$ ，并且 $C(n)-C(n-1)=n$ .故也合法且恰好用尽一到 $C(n)$ .

所有列从顶到底严格递减，因此逆向按编号从小到大放入，正好遵守原操作时序。构造与上界合起来证明最优数量就是 $C(n)$ .

## 按列生成

[std.cpp](std.cpp) 按输出顺序逐列计算上述构造。偶数规模先输出当前列的顶层球；最后一列随后结束，其余列进入奇数规模 $n-1$ .在奇数规模中输出上下两层的公式值；边缘列结束，内部列将局部列号减一、规模减二，继续下一层。规模变成一时输出球一。

这相当于沿某一列依次访问递归构造，公式与构造完全相同，所以输出正确。程序不保存整个方案，只用当前规模和列号。

![An optimal arrangement on four stacks](assets/stacks.svg)

时间为 $O(N^2)$ 次整数输出，额外空间为 $O(1)$ ，不计固定的输出缓冲。按位计的输出长度为 $O(N^2\log N)$ ；最大编号 $C(1000)=500999$ 可以用 32 位有符号整数表示。

## 另一种实现与来源

出题人解法采用同一分层构造，先保存整个方案再逐列输出。完整的[存储构造说明](solution-alternative.zh.md)及 [alternative.cpp](alternative.cpp) 一并保留，其时间同为 $O(N^2)$ 次整数操作，额外空间为 $O(N^2)$ .两份程序均支持完整范围。按列生成作为首选，明确节省辅助空间；这属于同一构造的实现改进，不是新的容量公式。

出题人解法：容量公式、奇偶分层构造及最优性思路。GPT-6：顶端区间的上界证明整理、按列输出实现、完整双语证明与方案校验器。小规模通过二分图最大匹配独立验证最大球数；完整数据检查编号唯一、递减顺序、平方和与最优总数。独立评测可运行 `python tests/checker.py input.in contestant.out` ，返回零表示接受，返回一表示拒绝。性能见[测量记录](../../../docs/benchmark-R24.json)。