← 返回题目列表

Codeforces · 1938/F

F. 形成团体

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Forming Groups - 原题 PDF 第 1 页
原题PDF第11页
Forming Groups - 原题 PDF 第 2 页
原题PDF第12页
可复制的 PDF 提取文本
Problem F
                   Forming Groups
                     Time limit: 5 seconds


There are n students, numbered from 1 to n, who need to form groups for the upcoming hackathon. You are student 1,
the captain of the students. Student i has skill level ai.

Students 2 to n are standing in a line from left to right in order. You can choose to stand in between any two students,
to the left of student 2, or to the right of student n. You cannot change the order of the n −1 students.

You can also choose the number of groups k (k > 1 and k must be a divisor of n) to participate in the hackathon. The
groups will be numbered from 1 to k. After you have chosen your position and the value of k, the students will be
grouped as follows:


     • The first student from the left will be assigned to group 1.

     • The second student from the left will be assigned to group 2.

     •  . . .

     • The k-th student from the left will be assigned to group k.

     • The (k + 1)-th student from the left will be assigned to group 1.

     • The (k + 2)-th student from the left will be assigned to group 2.

     •  . . .

     • The n-th student from the left will be assigned to group k.


Formally, for each j (1 ≤j ≤k) and for each i (0 ≤i < n/k), the (i×k +j)-th student from the left will be assigned
to group j. It can be shown that each student will be assigned to exactly one group and all the groups have the same
number of students.

The skill level of a group is the sum of the skill levels of the students inside the group. By choosing where you stand
as well as the number of groups k optimally, you want to minimize the ratio xmax/xmin where


     • xmax is the skill level of the group with the largest skill level, and

     • xmin is the skill level of the group with the smallest skill level.


Input

The first line of input contains one integer t (1 ≤t ≤100 000) representing the number of test cases. After that, t test
cases follow. Each of them is presented as follows.
The first line of a test case contains two integers n and a1 (2 ≤n ≤106; 1 ≤a1 ≤1000). The next line contains
n −1 integers a2, a3, . . . , an (1 ≤ai ≤1000 for all i).
The sum of n across all test cases in one input file does not exceed 106.



ICPC Asia Pacific Championship 2024 Problem F: Forming Groups

Output

For each test case, output one line containing two positive integers p and q such that the minimum ratio is p/q. The
fraction p/q should be irreducible. In other words, p and q should be coprime.


 Sample Input #1                          Sample Output #1
 2                                      1 1
 4 1                                    10 3
 2 1 2
 3 10
 4 3


Explanation for the sample input/output #1

In the first test case, by standing between students 2 and 3 (or between students 3 and 4) and choosing k = 2, group 1
will have the skill level 2 + 1 and group 2 will have the skill level 1 + 2, thus the ratio is 1/1.

In the second test case, the only choice for the value of k is 3.





ICPC Asia Pacific Championship 2024 Problem F: Forming Groups