P7282 [COCI 2020/2021 #4] Hop

> Jeremy is a bullfrog, and he is a good friend of mine.

There are $n$ lily pads, numbered from $1$ to $n$ in order. On the $i$-th pad there is an integer $x_i$, and the sequence $(x_i)_{1 \le i \le n}$ is strictly increasing. Three frogs arrive. Every pair of lily pads $(a,b)$ with $a \lt b$ must be assigned to exactly one of frogs $1,2,$ or $3$. If a pair $(i,j)$ is assigned to a frog and $x_j$ is divisible by $x_i$ ($j \gt i$), then that frog can jump from pad $i$ to pad $j$. Find an assignment such that no frog can make more than $3$ consecutive jumps.

The first line contains a positive integer $n$, the number of lily pads. The second line contains $n$ positive integers $x_i$, the integers on the lily pads.

Output $n-1$ lines. On line $i$, output $i$ integers, where the $j$-th integer on that line indicates which frog the pair $(j,i+1)$ is assigned to.

#### Explanation of Sample 1  Frogs $1,2,3$ are represented by blue, green, and red, respectively. The blue frog can jump from $x_1=3$ to $x_4=9$, then to $x_7=36$, and then to $x_8=72$. This frog can make only $3$ consecutive jumps. The green frog can jump from $x_2=4$ to $x_5=12$, and then to $x_7=36$. This frog can make only $2$ consecutive jumps. The red frog cannot jump from $x_2=4$ to $x_3=6$, because $6$ is not divisible by $4$. #### Constraints **This problem uses bundled evaluation.** | Subtask | Points | Constraints and notes | | :----------: | :----------: | :----------: | | $1$ | $10$ | $n \le 30$ | | $2$ | $100$ | None | For $100\%$ of the testdata, $1 \le n \le 1000$, $1 \le x_i \le 10^{18}$. #### Scoring In your output, if one frog can make $k$ consecutive jumps with $k \gt 3$, and no frog can make $k+1$ consecutive jumps, then the score for that test point is $f(k)·x$ points, where: $$f(k)=\dfrac{1}{10}· \begin{cases} 11-k & (4 \le k \le 5) \cr 8-\lfloor {\dfrac{k}{2}} \rfloor & (6 \le k \le 11) \cr 1 & (12 \le k \le 19) \cr 0 & (k \ge 20) \cr \end{cases}$$ Here, $x$ is the total score of the corresponding subtask. The score of each subtask equals the minimum score among all test points in that subtask. Because the scoring of this problem is special, a non-official self-written [Special Judge](https://www.luogu.com.cn/paste/mfhbmugl) is enabled. You can also download it from the attachments. Everyone is welcome to hack (you may send a private message or post directly). #### Notes **The points of this problem follow the original COCI setting, with a full score of $110$.** **Translated from [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/contest4_tasks.pdf) _T3 Hop_.** Translated by ChatGPT 5