假设有 n 根柱子,现要按下述规则在这 n 根柱子中依次放入编号为 1, 2, 3 … 的球。每次只能在某根柱子的最上面放球。同一根柱子中,任何 2 个相邻球的编号之和为完全平方数。 试设计一个算法,计算出在 n 根柱子上最多能放多少个球。例如,在 4 根柱子上最多可放 11 个球。对于给定的 n,计算在 n 根柱子上最多能放多少个球。 为了使得方案唯一,在依次放入球时,必须严格遵循以下贪心策略: 对于当前要放入的球,从第 1 根柱子到第 n 根柱子依次检查。 如果该球的编号与某根柱子最顶端的球的编号之和为完全平方数,则将该球放到这根柱子上,并停止检查。 如果所有已经放了球的柱子都无法满足条件,且当前使用的柱子数未达到 n,则将其放到一根新的空柱子上(新柱子编号为当前已用柱子数 + 1)。 如果所有 n 根柱子都无法满足条件,则游戏结束。
只有一行一个整数 n(1 ≤ n ≤ 55),代表柱子数。
请将 n 根柱子上最多能放的球数以及相应的放置方案输出(本题有特判)。 输出的第一行是球数。 接下来的 n 行,每行若干个整数,代表一根柱子上的球的编号,数字间用单个空格隔开。
4
11 1 8 2 7 9 3 6 10 4 5 11