20662번 - Hop 서브태스크점수다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 83 | 31 | 31 | 48.438% |
문제
♪ 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 ≤ 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 $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 ≤ n ≤ 1000$), the number of water lilies.
The second line contains $n$ positive integers $x_i$ ($1 ≤ x_i ≤ 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 ≤ 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) \cdot x$ points, where
$$f(k) = \frac{1}{10} \cdot \begin{cases} 11 - k & \text{if }4 ≤ k ≤ 5, \\ 8 - \lfloor k/2 \rfloor & \text{if }6 ≤ k ≤ 11, \\ 1 & \text{if }12 ≤ k ≤ 19, \\ 0 & \text{if } k ≥ 20, \end{cases}$$
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.
예제 입력 1
8 3 4 6 9 12 18 36 72
예제 출력 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
예제 입력 2
2 10 101
예제 출력 2
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 $x_1 = 3$ to water lily $x_4 = 9$, then to water lily $x_7 = 36$, and then to $x_8 = 72$. These are the only three consecutive hops any frog can make.
The green frog can hop from water lily $x_2 = 4$ to water lily $x_5 = 12$, and then to $x_7 = 36$, because $4$ divides $12$, and $12$ divides $36$. Those are two consecutive hops.
The red frog cannot hop from water lily $x_2 = 4$ to water lily $x_3 = 6$ because $6$ is not divisible by $4$.
No frog can make more than three consecutive hops.
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호