QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#144560#3206. Acperiencesomeaccaccount0 0ms0kbPython3794b2023-08-21 16:57:502023-08-21 17:00:19

Judging History

This is the latest submission verdict.

  • [2023-08-21 17:00:19]
  • Judged
  • Verdict: 0
  • Time: 0ms
  • Memory: 0kb
  • [2023-08-21 16:57:50]
  • Submitted

answer

from fractions import Fraction

for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    
    def chk(k):
        ret = 0
        for t in arr:
            if t >= 0:
                ret += (t - k) ** 2
            else:
                ret += (t + k) ** 2
        return ret
    
    l, r = 0, int(1e9)
    while r - l > 3:
        lo = (l + r) // 2
        hi = lo + 1
        
        loVal = chk(lo / n)
        hiVal = chk(hi / n)
        if loVal < hiVal:
            r = hi
        else:
            l = lo
    
    alpha, ans = 0, 1e18
    for i in range(l, r + 1):
        tmp = chk(Fraction(i, n))
        if tmp < ans:
            ans = tmp
            alpha = i
    print(f'{ans.numerator}/{ans.denominator}')

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

393
4
1 2 3 4
4
2 2 2 2
5
5 6 2 3 4
10
0 0 1 -1 -1 1 -1 1 -1 -1
10
-1 -1 -1 1 1 0 1 -1 -1 1
10
1 1 0 -1 0 1 0 1 -1 -1
10
0 0 0 1 -1 -1 1 1 1 1
10
-1 1 -1 -1 1 0 1 -1 -1 0
10
1 1 0 -1 1 -1 -1 -1 0 1
10
1 0 1 1 -1 -1 0 0 0 -1
10
-1 1 -1 -1 0 0 -1 1 1 1
10
0 -1 -1 0 -1 0 1 1 1 0
10
0 1 1 0 1 0 -1 1 1 1...

output:

5/1
0/1
10/1
8/5
9/10
21/10
21/10
8/5
8/5
12/5
8/5
12/5
21/10
12/5
5/2
21/10
21/10
21/10
8/5
21/10
21/10
5/2
12/5
12/5
12/5
5/2
12/5
12/5
8/5
12/5
5/2
21/10
21/10
21/10
21/10
12/5
9/10
8/5
9/10
12/5
21/10
8/5
12/5
21/10
9/10
5/2
5/2
12/5
21/10
21/10
21/10
21/10
21/10
12/5
5/2
12/5
8/5
8/5
21/10
21/1...

result: