Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

pile of cards

Mohit LalwaniMohit Lalwani Member Posts: 1

There are several piles of cards on the table arranged from left to right. All of them do not contain the same number of cards. As the boss insists on symmetry, Ramu is asked to merge the minimum number of adjacent piles so that if a list of the number of cards in each pile is given in left to right order, the list reads the same whether it is read in the left to right order or the right to left order.

For example, if the piles of cards initially were 1 2 2 5 1 3 1 1, there can be three merges (2,2), (5,1) and (3,1) to give 1 4 6 4 1.
Note that merging 3 numbers, say (1,2,2) is counted as 2 merges, one between (1 2) and the next between the resulting 3 and the next two. Hence another solution (1,2,2) (5,1) (3,1,1) resulting in 5 6 5 takes 2 + 2 + 1 or 5 merges, and is not minimal.

Another (trivial) solution is to merge all the piles to give 16. This may be the only solution in some cases, and shows that all initial sets have at least one (not necessarily minimal) solution

Input

There are two lines.
The first line is the number of piles.
The next line contains space separated positive integers, representing the numbers of cards in the piles from left to right.

Output

If the minimal merge results in more than one pile, the output has two lines, the first giving one integer (the number of merges) and the second containing space separated integers, giving the number of cards in the final pile sequence in order (left to right).
If there is no solution other than merging all into one pile, the output will be a single line containing the letters "TRIVIAL MERGE".

Constraints

The initial number of piles will be less than 50, and the number of cards in each pile in the initial configuration will be less than 1000.

Example 1

Input:
8
1 4 3 6 1 2 1 5

Output:
3
5 3 7 3 5

Sign In or Register to comment.