17670번 - 난 서브태스크스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 256 MB | 152 | 47 | 38 | 27.941% |
문제
JOI 카레 매점은 매우 긴 난(인도의 납작한 빵)을 판매하는 것으로 유명하다. 난에는 $L$개의 맛이 있으며, 1번부터 $L$번까지 번호가 붙어 있다. 난 중에서 "JOI 스페셜 난"이 제일 인기가 있다. 길이가 $L$cm 이고, 왼쪽에서 $j-1$cm 부터 $j$cm 까지 부분에는 $j$번 ($1\le j \le L$) 맛으로 되어 있다.
$N$명의 사람이 JOI 카레 매점에 왔다. 그들의 취향은 다른 사람과 다르다. 구체적으로, $i$ 번째 ($1 \le i \le N$) 사람이 $j$번 ($1 \le j \le L$) 맛의 난을 먹었을 경우에는, 1 cm당 $V_{i, j}$의 행복도를 얻을 것이다. 그들은 하나의 JOI 스페셜 난을 주문했다. 그들은 난을 다음과 같은 방법으로 나누어 가질 것이다.
- $0 < X_1 < X_2 < \cdots < X_{N-1} < L$을 만족하는 $N-1$개의 분수 $X_1,\ \cdots,\ X_{N-1}$를 고른다.
- $N$개의 정수 $P_1,\ \cdots, \ P_N$을 고른다. 이는 $1, \ \cdots, \ N$의 순열이어야 한다.
- 각 $k$ ($1 \le k \le N-1$)에 대해서, 난을 $X_k$지점에서 자른다. 난은 $N$개의 조각으로 나누어질 것이다.
- 각 $k$ ($1 \le k \le N$)에 대해서, $P_k$번째 사람에게 $X_{k-1}$과 $X_k$ 사이의 조각을 준다. 우리는 $X_0$을 0, $X_N$을 $L$이라고 생각할 것이다.
우리는 난을 공평하게 나누고 싶다. 우리는 각 사람이 혼자 JOI 스페셜 난을 모두 먹었을 때 얻는 행복도의 $1/N$이상을 얻었을 경우, 분배 방식이 공평하다고 할 것이다.
$N$명의 사람의 선호가 주어졌을 때, 난을 공평하게 나누는 방법이 있는가를 출력하여라. 있는 경우, 난을 공평하게 나누는 방법에 대해 출력하여라.
입력
표준 입력에서 다음과 같은 형식으로 주어진다. 모든 수는 정수이다.
$N$ $L$
$V_{1,1}$ $V_{1, 2}$ $\cdots$ $V_{1, L}$
$\vdots$
$V_{N,1}$ $V_{N, 2}$ $\cdots$ $V_{N, L}$
출력
난을 공평하게 나누는 방법이 없다면, -1을 첫째 줄에 출력하여라. 공평하게 나눌 수 있다면, 나누는 방법을 나타내는 $N-1$개의 분수 $X_1,\ \cdots,\ X_{N-1}$과 $N$개의 정수 $P_1, \cdots, P_N$을 다음 형식으로 출력하여라.
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_{N-1}$ $B_{N-1}$
$P_1$ $P_2$ $\cdots$ $P_N$
$A_i$, $B_i$는 $X_i = \dfrac{A_i}{B_i}$ ($1 \le i \le N$)를 만족하는 정수 쌍이다. 이 정수는 출력 제한을 따라야 한다.
제한
입력 제한
- $1 \le N \le 2000$.
- $0 \le L \le 2000$.
- $1 \le V_{i, j} \le 100\ 000$ ($1 \le i \le N,\ 1 \le j \le L$).
출력 제한
난을 공평한 방식으로 나눈 방법이 존재한다면, 출력은 다음 제한을 따라야 한다.
- $1 \le B_i \le 1\ 000\ 000\ 000$. ($1 \le i \le N$)
- $0 \le \dfrac{A_1}{B_1} < \dfrac{A_2}{B_2} \cdots < \dfrac{A_{N-1}}{B_{N-1}} < L$.
- $P_1, \ \cdots, \ P_N$은 $1, \ \cdots, \ N$의 순열이다.
- 분배에서, $i$번째 사람이 가지는 행복도의 양은 $\dfrac{V_{i, 1}+V_{i,2}+\cdots+V_{i,L}}{N}$ 이상 이어야 한다.
$A_i$와 $B_i$는 서로소일 필요는 없다. 아래 제한 하에서, 공평한 분배가 존재 할 경우 $1 \le B_i \le 1\ 000\ 000\ 000$을 만족하는 출력이 존재함을 증명할 수 있다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | N = 2. |
| 2 | 24 | N ≤ 6, Vi,j ≤ 10 (1 ≤ i ≤ N, 1 ≤ j ≤ L). |
| 3 | 71 | No additional constraints. |
예제 입력 1
2 5 2 7 1 8 2 3 1 4 1 5
예제 출력 1
14 5 2 1
이 예제에서, 모든 난을 먹었을 때, 첫째 사람은 2 + 7 + 1 + 8 + 2 = 20의 행복도를 가지고 둘째 사람은 3 + 1 + 4 + 1 + 5 = 14의 행복도를 가진다. 즉, 첫째 사람이 $\dfrac{20}{2} = 10$ 이상의 행복도를 가지고 둘째 사람이 $\dfrac{14}{2} = 7$ 이상의 행복도를 가지면, 분배는 공평하다.
난을 $\dfrac{14}{5}$에서 나누면, 첫째 사람은 $1 \times \dfrac{1}{5} + 8 + 2 = \dfrac{51}{5}$의 행복도를 얻고, 둘째 사람은 $3 + 1 + 4 \times \dfrac{4}{5} = \dfrac{36}{5}$의 행복도를 얻는다. 그러므로, 이것은 공평한 분배이다.
예제 입력 2
7 1 1 2 3 4 5 6 7
예제 출력 2
1 7 2 7 3 7 4 7 5 7 6 7 3 1 4 2 7 6 5
이 예제에서는 맛이 하나 뿐이다. 난을 크기가 같은 7개의 부분으로 자르면, $P_1, \ \cdots, \ P_N$과 관계 없이 분배가 공정하다.
예제 입력 3
5 3 2 3 1 1 1 1 2 2 1 1 2 2 1 2 1
예제 출력 3
15 28 35 28 50 28 70 28 3 1 5 2 4
$A_i$와 $B_i$가 서로소 일 필요는 없다. ($1 \le i \le N$)
출처
Camp > JOI Spring Training Camp > JOI 2018/2019 Spring Training Camp 1-3번
- 문제를 번역한 사람: ho94949
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호