레이팅 미적용♪Jeremiah was \(a\) bullfrog
Was \(a\) good friend \(of\) mine ♪
There are \(n\) water lilies, numbered 1 through \(n\), in a line. On the \(i\)-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.
The first line contains a positive integer \(n\) (\(1 \le n \le 1000\)), 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 \(n - 1\) lines. In the \(i\)-th line, output \(i\) numbers, where the \(j\)-th number is the label of the frog to
which (j, \(i + 1\)) belongs.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
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\)) · \(x\) points, where \(f\)(\(k\)) = ^{1} 10 ^{·} \(11 - k\) if \(4 \le k \le 5\), 8 −⌊\(k/2\)⌋ if \(6 \le k \le 11\), 1 if \(12 \le k \le 19\), 0 if \(k \ge 20\), 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. |
8
3 4 6 9 12 18 36 72
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
2
10 101
1