Restoring Equal-Length Sticks
Time limit1sMemory limit128 MB
Given stick pieces, find the smallest common stick length so all pieces can be partitioned into groups summing to that length, and output the grouping.
- Level
Medium6 of 10
- Topics
- Backtracking, Math, Brute force
- Solved
- No attempts yet
Problem
Seungyeon had several sticks whose lengths were integers. Each stick was cut into several integer-length pieces, although some sticks may not have been cut at all.
Now all pieces must be joined back into sticks of one common length. However, the original number of sticks and their length have been forgotten. Find the shortest possible common stick length that can be formed by using every piece exactly once.
For example, if the piece lengths are {5, 2, 1, 1, 2, 5, 2, 5, 1}, it is possible to make two sticks of length 12, but the shortest possible common length is 6.
Input
The input consists of two lines. The first line contains the number of pieces, n. The value of n is at most 50.
The second line contains the length l of each piece, separated by spaces. Every length is an integer satisfying 1 <= l <= 1,000.
Output
Print the length of one restored stick on the first line.
Then print one restored stick per line, listing the lengths of the pieces that make up that stick. The order of pieces within a line and the order of the stick lines may be arbitrary.