TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1939
  • 题目
  • P1939【线性规划与网络流24题 4】魔术球
    限制 : 时间限制 : 1000 MS   空间限制 : 65536 KB
    问题描述

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

    由于本OJ无Special Judge , 所以只需要输出最多能放的球的个数

    输入格式

    第1 行有 1个正整数n,表示柱子数。(0<n<60)

    输出格式

    /
    程序运行结束时,将 n 根柱子上最多能放的球数以及相应的放置方案输出。
    文件的第一行是球数。接下来的n行,每行是一根柱子上的球的编号。
    按字典序输出方案
    /
    一行,包含一个整数,表示最多能放的球数

    样例输入

    4

    样例输出

    11
    /*
    1 8
    2 7 9
    3 6 10
    4 5 11
    */

    提示

    无视被/* */包括的内容


    来源  感谢 Wo_ai_WangYuan 修改题目并放上数据