top of page

CCC 2017 J5 and S3: Nailed It!

The solution:

This is a counting sort problem.

we can define two lists:

L = [0]*2001 F = [0]*4001

L is a list, its index is each wood's length, its element value is the number of this length. The max index 2000 is one wood's max length.

F is a list, its index is two wood's length that is one block fence, its element value is the number of this fence length. The max index 4000 is two woods max length.


Assume input a wood its length is p, then L[p] += 1, because length p has one wood.

For loop i from 0 to the end of L , i is the length of each wood

for loop j from i to the end of L, j is the length of each wood too

if i == j, F[i+j] = L[i]//2, i+j is one fence's length

if i != jh, F[i+j] = min(L[i], L[j]), i+j is one fence's length


For loop F, find max length and block number

print max length and block number


N = int(input())
boards = input().split(" ")
L = [0]*2001
F = [0]*4001

for board in boards:
    L[int(board)] += 1

for i in range(0, len(L) - 1):
    for j in range(i, len(L)):
        if i == j:
            F[i + j] += L[i] // 2
        else:
            F[i + j] += min(L[i], L[j])

longest, size = 0, 0

for fenceLength in F:
    if fenceLength > longest:
        longest = fenceLength
        size = 1
    elif fenceLength == longest:
        size += 1

print(longest, size)

Recent Posts

See All

Comments


bottom of page