同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1616_魔术球

2022-5-16 18:17| 发布者: Hocassian| 查看: 32| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-8950445581799-Problem List-采集的数据-后羿采集器.html

Pro.ID

1616

Title

魔术球

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1616

AC

Submit

Ratio

0.00%

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

描述

假设有 n 根柱子，现要按下述规则在这 n 根柱子中依次放入编号为 1, 2, 3, 4, ⋯ 的球。

每次只能在某根柱子的最上面放球。
在同一根柱子中，任何 2 个相邻球的编号之和为完全平方数。

试设计一个算法，计算出在 n 根柱子上最多能放多少个球。

输入

第 1 行有 1 个正整数 n ，表示柱子数。 1 ≤ n ≤ 55

输出

Description

假设有 n 根柱子，现要按下述规则在这 n 根柱子中依次放入编号为 1, 2, 3, 4, ⋯ 的球。

每次只能在某根柱子的最上面放球。
在同一根柱子中，任何 2 个相邻球的编号之和为完全平方数。

试设计一个算法，计算出在 n 根柱子上最多能放多少个球。

Input

第 1 行有 1 个正整数 n ，表示柱子数。 1 ≤ n ≤ 55

Output

第一行是球数。接下来的 n 行，每行是一根柱子上的球的编号。

Sample Input

Sample Output

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

Source

网络流 24 题

样例输入

样例输出