COCI '20 Contest 4 #3 Hop

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

There are n water lilies, numbered 1 through n, in a line. On the i^\text{th} lily there is a positive integer x_i, and the sequence (x_i)_{1 \le i \le n} is strictly increasing.

Enter three frogs.

Every pair of water lilies (a, b), where a < b, must belong to frog 1, frog 2, or frog 3.

A frog can hop from water lily i to water lily j > i if the pair (i, j) belongs to it, and x_i divides x_j.

Distribute the pairs among the frogs such that no frog can make more than 3 consecutive hops.

Input Specification

The first line contains a positive integer n (1 \le n \le 1\,000), the number of water lilies.

The second line contains n positive integers x_i (1 \le x_i \le 10^{18}), the numbers on the water lilies.

Output Specification

Output n-1 lines. In the i^\text{th} line, output i numbers, where the j^\text{th} number is the label of the frog to which (j, i+1) belongs.

Constraints

Subtask Points Constraints
1 10 n \le 30
2 100 No additional constraints.

If in your solution some frog can make k consecutive hops, where k > 3, but no frog can make k+1 consecutive hops, your score for that test case is f(k) \cdot x points, where

\displaystyle f(x) = \frac{1}{10} \cdot \begin{cases}
11-k & \text{if } 4 \le k \le 5 \\
8-\lfloor k/2 \rfloor & \text{if } 6 \le k \le 11 \\
1 & \text{if } 12 \le k \le 19 \\
0 & \text{if } k \ge 20
\end{cases}

and x is the number of points for that subtask.

The score for some subtask equals the minimum score which your solution gets over all test cases in that subtask.

Sample Input 1

8
3 4 6 9 12 18 36 72

Sample Output 1

1
2 3
1 2 3
1 2 3 1
2 3 1 2 3
1 2 3 1 2 3
1 2 3 1 2 3 1

Explanation

1

The frogs are marked blue (1), green (2), and red (3).

The blue frog can hop from water lily x_1 = 3 to water lily x_4 = 9, then to water lily x_7 = 36, and then to x_8 = 72. These are the only three consecutive hops any frog can make.

The green frog can hop from water lily x_2 = 4 to water lily x_5 = 12, and then to x_7 = 36, because 4 divides 12, and 12 divides 36. Those are two consecutive hops.

The red frog cannot hop from water lily x_2 = 4 to water lily x_3 = 6 because 6 is not divisible by 4.

No frog can make more than three consecutive hops.

Sample Input 2

2
10 101

Sample Output 2

1

Comments

There are no comments at the moment.