A1387. [COCI-2020-2021-contest4]#1 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.
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.
输入格式
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.
The second line contains n positive integers xi (1 ≤ xi ≤ 1018), 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
8 3 4 6 9 12 18 36 7
输出 #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.
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.