QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#676490#8790. First BillionmalkovskyTL 27ms10832kbPython31.3kb2024-10-25 21:48:412024-10-25 21:48:41

Judging History

你现在查看的是最新测评结果

  • [2024-10-25 21:48:41]
  • 评测
  • 测评结果:TL
  • 用时:27ms
  • 内存:10832kb
  • [2024-10-25 21:48:41]
  • 提交

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

output:


result: