COCI 2020/2021 - Contest 4 - Hop

View as PDF

Submit solution

Points: 1.40 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2020/2021 - Contest 4
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Có ~n~ lá sen được đánh số từ ~1~ đến ~n~ xếp thành 1 hàng ngang. Trên lá sen thứ ~i~ có 1 số nguyên ~x_i~, và dãy ~(x_i)_{1\leq i \leq n}~ là dãy tăng ngặt.

Đặt 3 chú ếch lên những lá sen.

Mỗi cặp lá sen ~(a,b), a \leq b~, phải thuộc về 1 trong 3 chú ếch.

Chú ếch có thể nảy từ lá sen ~i~ sang lá sen ~j~, ~(i < j)~. Nếu cặp ~(i,j)~ thuộc về nó, đồng thời ~x_j~ chia hết cho ~x_i~

Hãy phân phối các cặp chỉ số cho những chú ếch sao cho không có chú ếch nào có thể nhảy từ lá sen này sang lá sen khác quá 3 lần liên tục.

Input

Dòng đầu tiên chứa ~1~ số nguyên ~n (1 \leq n \leq 1000)~ là số lá sen.

Dòng thứ 2 chứa ~n~ số nguyên dương ~x_i~ ~(1 \leq x_i \leq 10^{18})~ là các số nguyên ở trên từng lá sen.

Output

Xuất ra ~n-1~ dòng.

Ở dòng thứ ~i~ xuất ra ~i~ số, số thứ ~j~-th là chỉ số của chú ếch mà cặp lá sen ~(j,i+1)~ thuộc về nó.

Sample 1

Input
8
3 4 6 9 12 18 36 72
Output
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

Sample 2

Input
2
10 101
Output
1

Giải thích

Ở ví dụ đầu tiên:

Ta sẽ xét những chú ếch như sau: ếch số 1 màu xanh biển, ếch số 2 màu xanh lá, ếch số 3 màu đỏ.

Chú ếch xanh biển có thể nhảy từ lá sen có ~x_1 = 3~ tới lá sen ~x_4 = 9~ rồi nhảy sang lá sen ~x_7 = 36~ rồi tới lá sen ~x_8 = 72~. Đây là 3 cú nhảy liên tiếp duy nhất mà chú ếch nào cũng thực hiện được.

Chú ếch xanh lá có thể bắt đầu từ lá sen ~x_2 = 4~ tới lá sen ~x_5 = 12~ rồi tới ~x_7 = 36~ (vì 12 chia hết cho 4 và 36 chia hết cho 12).Tổng cộng có 2 lần nhảy liên tiếp.

Chú ếch đỏ không thể nhảy từ lá sen có ~x_2 = 4~ đến lá sen có ~x_3=6~ vì 6 không chia hết cho 4.

Không có chú ếch nào có thể thực hiện quá 3 lần nhảy liên tiếp.

Subtask

  • ~6~ test đầu tiên có ~n \leq 30~.
  • ~17~ test còn lại không ràng buộc gì thêm.

Nếu trong đáp án của bạn một vài chú ếch có thể thực hiện ~k~ cú nhảy liên tiếp,~k > 3~, nhưng không có chú ếch khác nào có thể thực hiện ~k+1~ cú nhảy liên tiếp thì số điểm bạn nhận được cho test đó là ~f(k)\times x~.

~f(k)~ được xác định bởi:

~f(k) = \frac{1}{10} \times \begin{cases} {11 - k} & {(4 \leq k \leq 5)},\\ {8 - \lfloor k/2 \rfloor }&(6 \leq k \leq 11),\\ {1}&{(12 \leq k \leq 19)},\\ {0}&{(k \geq 20)} \end{cases}~

và ~x~ là số điểm của test đó.

Điểm của test là= ~f(k) \times x~. Điểm của bài là tổng điểm các test.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.