Packing the Boxes
All submissions for this problem are available.
Shaheen has bought some gifts for a friend, which are wrapped up in several boxes of different sizes (all of which are full). She will need to carry the gifts a long way to her friend's house, so she would prefer to add some extra packing, and accommodate everything in one extra box. Moreover, to avoid damaging the contents, she does not wish to place more than two boxes directly within any box; however, boxes can be placed within boxes which contain other boxes, etc. A box which is used for holding two boxes of sizes a and b will have size a+b, and will cost Shaheen a+b coins at the local store. Please help Shaheen determine the minimum cost required to achieve the complete packing, and the number of different possible packings (arrangements of boxes within each other) having such a minimal cost.
The first line of input is n <=2000, the number of boxes with Shaheen's gifts. The next n lines of input contain one positive integer each, not greater than 106, representing the sizes of the successive boxes.
Print to output exactly 2 numbers separated by spaces: the cost of the optimal solution, and the number of distinct ways of achieving this solution (modulo 109).
Input: 5 3 2 3 5 1 Output: 31 3
The three solutions leading to cost 31 are as follows:
1) pack the 2nd and the 5th box together, pack the resulting box together with the 1st box, and pack the result together with an additional box used for packing the 3rd and 4th boxes,
2) pack the 2nd and the 5th box together, pack the resulting box together with the 3rd box, and pack the result together with an additional box used for packing the 1st and 4th boxes,
3) pack the 2nd and the 5th box together, pack the resulting box together with the 4th box, and pack the result together with an additional box used for packing the 1st and 3rd boxes.
|Time Limit:||0.422619 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, CS2, PAS fpc, PAS gpc, RUBY, PHP, HASK, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, TEXT|
Fetching successful submissions