[网络流24题]魔术球问题(简化版

Grade Open Time Friday, 19 September 2014, 10:04 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:04 am
Allow late Yes Close Time Friday, 26 September 2014, 10:04 am
Input file balla.in Output file 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

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


本题原版