P2765 Magic Ball Problem

Assume there are $n$ rods. We insert balls labeled $1$, $2$, $3$, ... into these $n$ rods in order, following the rules below: 1. Each time, you can only place a ball on the top of some rod. 2. On the same rod, the sum of the labels of any $2$ adjacent balls is a perfect square. Design an algorithm to compute the maximum number of balls that can be placed on $n$ rods. For example, with $4$ rods, at most $11$ balls can be placed. Given $n$, compute the maximum number of balls that can be placed on $n$ rods.

There is only one line containing an integer $n$, representing the number of rods.

**This problem has a Special Judge.** Please output the maximum number of balls that can be placed on $n$ rods, along with a corresponding placement scheme. The first line is the number of balls. The next $n$ lines each contain several integers, representing the labels of the balls on one rod, separated by a single space.

Constraints For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 55$. Translated by ChatGPT 5