#P2765. 魔术球问题

    ID: 5074 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>网络流Special JudgeO2优化最大流网络流 24 题

魔术球问题

题目描述

假设有 nn 根柱子,现要按下述规则在这 nn 根柱子中依次放入编号为 112233,...的球“

  1. 每次只能在某根柱子的最上面放球。

  2. 同一根柱子中,任何 22 个相邻球的编号之和为完全平方数。

试设计一个算法,计算出在 nn 根柱子上最多能放多少个球。例如,在 44 根柱子上最多可放 1111 个球。

对于给定的 nn,计算在 nn 根柱子上最多能放多少个球。

输入格式

只有一行一个整数 nn,代表柱子数。

输出格式

本题存在 Special Judge

请将 nn 根柱子上最多能放的球数以及相应的放置方案输出。

输出的第一行是球数。

接下来的 nn 行,每行若干个整数,代表一根柱子上的球的编号,数字间用单个空格隔开。

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

提示

数据规模与约定

对于 100%100\% 的数据,保证 1n551 \leq n \leq 55