平方和球柱：分层构造与按列输出¶
最大数量的证明¶
记 \(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\) ：
再在中间 \(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 按输出顺序逐列计算上述构造。偶数规模先输出当前列的顶层球；最后一列随后结束，其余列进入奇数规模 \(n-1\) .在奇数规模中输出上下两层的公式值；边缘列结束，内部列将局部列号减一、规模减二，继续下一层。规模变成一时输出球一。
这相当于沿某一列依次访问递归构造，公式与构造完全相同，所以输出正确。程序不保存整个方案，只用当前规模和列号。
时间为 \(O(N^2)\) 次整数输出，额外空间为 \(O(1)\) ，不计固定的输出缓冲。按位计的输出长度为 \(O(N^2\log N)\) ；最大编号 \(C(1000)=500999\) 可以用 32 位有符号整数表示。
另一种实现与来源¶
出题人解法采用同一分层构造，先保存整个方案再逐列输出。完整的存储构造说明及 alternative.cpp 一并保留，其时间同为 \(O(N^2)\) 次整数操作，额外空间为 \(O(N^2)\) .两份程序均支持完整范围。按列生成作为首选，明确节省辅助空间；这属于同一构造的实现改进，不是新的容量公式。
出题人解法：容量公式、奇偶分层构造及最优性思路。GPT-6：顶端区间的上界证明整理、按列输出实现、完整双语证明与方案校验器。小规模通过二分图最大匹配独立验证最大球数；完整数据检查编号唯一、递减顺序、平方和与最优总数。独立评测可运行 python tests/checker.py input.in contestant.out ，返回零表示接受，返回一表示拒绝。性能见测量记录。