QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#144560 | #3206. Acperience | someaccaccount | 0 | 0ms | 0kb | Python3 | 794b | 2023-08-21 16:57:50 | 2023-08-21 17:00:19 |
Judging History
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...