魔术球问题

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23: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

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