QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#676490 | #8790. First Billion | malkovsky | TL | 27ms | 10832kb | Python3 | 1.3kb | 2024-10-25 21:48:41 | 2024-10-25 21:48:41 |
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(len(answer), end=" ")
for num in answer:
print(num + 1, end=" ")
__main__()
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 10ms
memory: 10692kb
input:
10 386413329 88494216 245947398 316438989 192751270 204627269 65749456 3938400 150458676 345180997
output:
5 9 7 6 5 1
result:
ok OK (n = 10)
Test #2:
score: 0
Accepted
time: 10ms
memory: 10668kb
input:
10 119486233 299942886 169540407 349937991 597883752 32230162 140514533 57341098 12602102 220520836
output:
5 9 8 6 5 2
result:
ok OK (n = 10)
Test #3:
score: 0
Accepted
time: 21ms
memory: 10724kb
input:
14 384615281 84612238 83310504 54746763 142296081 56775470 128760350 343006424 177232390 214368720 67220468 21895072 16352717 224807522
output:
7 13 12 10 9 7 6 1
result:
ok OK (n = 14)
Test #4:
score: 0
Accepted
time: 27ms
memory: 10832kb
input:
14 270208635 14270307 89661499 113578022 47687195 101043954 38775146 208193324 650676076 351701957 3427619 59535626 24230888 27009752
output:
7 12 10 6 4 3 2 1
result:
ok OK (n = 14)
Test #5:
score: -100
Time Limit Exceeded
input:
20 61638928 106712373 5946815 178135484 4937573 111395400 15504655 67139983 101814514 312223647 130341028 43244171 37671364 54108486 337181317 37924824 153793862 70383750 102917244 66984582