#2173. Hop
Hop
Hop
题目描述
Croatian Open Competition in Informatics Task Hop Round 4, January 16th 2021 1 second / 512 MiB / 110 points Task Hop ♪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 xi, and the sequence (xi)1≤i≤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 xi divides xj. Distribute the pairs among the frogs such that no frog can make more than 3 consecutive hops. Input The first line contains a positive integer n (1 ≤n ≤1000), the number of water lilies. The second line contains n positive integers xi (1 ≤xi ≤1018), the numbers on the water lilies. Output 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. Scoring Subtask Points Constraints n ≤30 1 10 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 11 −k if 4 ≤k ≤5, 8 −⌊k/2⌋ if 6 ≤k ≤11, f(k) = 1 10 · if 12 ≤k ≤19, 1 if k ≥20, 0 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. 3 of 8 Croatian Open Competition in Informatics Task Hop Round 4, January 16th 2021 1 second / 512 MiB / 110 points Examples input input 8 2 3 4 6 9 12 18 36 72 10 101 output 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 Clarification of the first example: The frogs are marked blue (1), green (2), and red (3). The blue frog can hop from water lily x1 = 3 to water lily x4 = 9, then to water lily x7 = 36, and then to x8 = 72. These are the only three consecutive hops any frog can make. The green frog can hop from water lily x2 = 4 to water lily x5 = 12, and then to x7 = 36, because 4 divides 12, and 12 divides 36. Those are two consecutive hops. The red frog cannot hop from water lily x2 = 4 to water lily x3 = 6 because 6 is not divisible by 4. No frog can make more than three consecutive hops. 4 of 8
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
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
2
10 101
1