魔术球问题

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 balla.in 输出文件 balla.out

问题描述:
假设有n根柱子,现要按下述规则在这n根柱子中依次放入编号为 1,2,3,4......的球。
(1)每次只能在某根柱子的最上面放球。
(2)在同一根柱子中,任何2个相邻球的编号之和为完全平方数。
试设计一个算法,计算出在n根柱子上最多能放多少个球。例如,在4 根柱子上最多可
放11个球。
´编程任务:
对于给定的n,计算在 n根柱子上最多能放多少个球。

´数据输入:
文件第1 行有 1个正整数n,表示柱子数。
´结果输出:
文件的第一行是球数。

数据规模

n<=60  保证答案小于1600

输入文件示例

4

输出文件示例

11

方案如下

1 8
2 7 9
3 6 10
4 5 11

每一行表示一个柱子上的球