QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#676476 | #8790. First Billion | malkovsky | WA | 10ms | 10788kb | Python3 | 1.2kb | 2024-10-25 21:44:54 | 2024-10-25 21:44:54 |
Judging History
answer
def knapsap_mod(nums, mod):
numbers = [num % mod for num in nums]
dp = [[0 for i in range(mod)] for _ in range(len(numbers) + 1)]
dp[0][0] = 1
for i in range(len(numbers)):
for j in range(mod):
if dp[i][j] == 1:
dp[i + 1][(j + numbers[i]) % mod] = 1
dp[i + 1][(j + mod - numbers[i]) % mod] = 1
# print(dp[len(numbers)][0])
if dp[len(numbers)][0] == 1:
result = []
n = len(numbers)
cur = 0
while n > 0:
left = (cur + (mod - numbers[n - 1])) % mod
right = (cur + numbers[n - 1]) % mod
if dp[n - 1][left] == 1:
cur = left
else:
cur = right
result.append(n - 1)
n -= 1
return result
def __main__():
n = int(input())
numbers = list(map(int, input().split()))
answer = []
for mod in range(1001, 2001):
result = knapsap_mod(numbers, mod)
# print(result, sum([numbers[i] for i in result]) % mod)
if sum([numbers[i] for i in result]) == 1000000000:
answer = result
break
# print(num_at_least_k)
print(answer)
__main__()
详细
Test #1:
score: 0
Wrong Answer
time: 10ms
memory: 10788kb
input:
10 386413329 88494216 245947398 316438989 192751270 204627269 65749456 3938400 150458676 345180997
output:
[8, 6, 5, 4, 0]
result:
wrong output format Expected integer, but "[8," found