A1387 | [COCI-2020-2021-contest4]#1 Hop
来源COCI
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
♪ 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.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted