| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 512 MB | 273 | 149 | 122 | 55.963% |
Albert는 고양이 $N$ 마리를 키우고 있는데 편의상 번호가 1부터 $N$까지 붙어있다. 오늘은 간식으로 고양이용 과자 $M$개를 나눠주려고 하는데 각 과자는 1번 부터 $M$번까지 번호가 붙어있고, 모두 동일한 크기이다. $j$ 번째 과자는 균등한 크기의 $V_j$ 조각으로 쪼개져있고, 이는 $N$ 마리의 고양이들이 적절히 나눠먹는다 - $i$번째 고양이가 먹은 $j$번 과자 조각의 수를 $A_{j, i}$라 하자. 이 때, $\sum_{1 \le i \le N} A_{j, i} = V_j$ 를 항상 만족한다.
예를 들어 $N = 3,ドル $M = 3,ドル $V = [2, 3, 5],ドル $A = [ [0, 1, 1], [1, 2, 0], [2, 1, 2] ]$ 라 하자.
Albert는 고양이들이 모두 간식을 먹은 후 가장 많이 먹은 고양이와 가장 적게 먹은 고양이가 먹은 양의 차이가 궁금하다. 위 예제에서는 2번 고양이가 가장 많이 먹었고 1번 고양이가 가장 적게 먹었는데, 그 차이는 (19/30)개이다. Albert를 도와주자.
입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $N$과 $M$이 공백으로 구분되어 주어진다. 다음 $M$줄에 걸쳐 $j$번재 줄은 $j$번째 과자의 조각 수를 나타내는 $V_j$와 함께 $N$마리의 고양이들이 몇 조각씩 먹었는지 알려주는 $A_{j, \cdot}$ 배열의 값이 주어진다 -- 즉, 총 $N+1$ 개의 정수가 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답을 기약 분수 형태로 출력한다. 단, 답이 정수인 경우 정수 형태로 출력한다 (예제 참고).
5 3 3 10 0 4 6 5 0 3 2 2 2 0 0 3 3 2 0 1 1 3 1 2 0 5 2 1 2 5 1 9 1 2 3 2 1 3 2 1 1 0 0 4 0 2 2 3 3 1 1 0 0 4 0 0 4 3 0 0 3
0 19/30 2/9 1/2 2
예제 1 - 모든 고양이가 정확히 1개씩의 과자를 먹었으므로 최댓값과 최솟값의 차이는 0이다. 답이 정수이므로 정수를 그대로 출력한다.
예제 2 - 본문에서 다루었다.
예제 3 - 가장 많이 먹은 고양이는 (3/9) = (1/3) 개를 먹었고 가장 적게 먹은 고양이는 (1/9)개를 먹었으므로 그 차이인 2/9를 출력한다.
예제 4 - 세 마리가 각각 1개, 1/2개, 1개씩 먹었다.
예제 5 - 세 마리가 각각 1개, 0개, 2개씩 먹었다.
기약 분수 - 이 문제에서 답이 정수가 아닌 분수일 경우 $p/q$ 꼴인 기약 분수로 출력해야하며, 기약 분수란 $p, q$의 최대 공약수가 1인 경우를 이야기한다. 예제 3의 경우 2/9 가 정답이며 4/18 이나 6/27 등은 기약 분수가 아니므로 정답으로 인정하지 않는다.