• 56

## Goal

You have a list of natural numbers of size N and you must distribute the values in two lists A and B of size N/2, so that the squared sum of A elements is the nearest possible to the multiplication of the B elements.

Example:
Consider the list 7 11 1 9 10 3 5 13 9 12.
The optimized distribution is:
List A: 5 9 9 12 13
List B: 1 3 7 10 11

which leads to the difference abs( (5+9+9+12+13)^2 - (1*3*7*10*11) ) = 6
Your program should therefore output 6, which is the minimum difference that can be achieved.
Input
Line 1: The list size N
Line 2: N space separated natural numbers
Output
Line 1: The minimal difference between the squarred sum of elements in list A and the multiplication of elements in list B.
Constraints
1 <= N <= 40
0 < value of a list element < 21
N is always even, so size(A) = size(B).
There is at most 12 different natural numbers.
Example
Input
10
7 11 1 9 10 3 5 13 9 12
Output
6

A higher resolution is required to access the IDE

Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
Online Participants