All submissions for this problem are available.
Vinod is bored, so he decided to play a quick game. He has a sequence 'S' consisting of N integers and an empty array A.
In each step Vinod removes either first or last number of sequence S and adds it at the end of the array A. This game continues till there are no more numbers left in S. In the end of the game, array A has N numbers.
Now maximum of 2n-1 permutations of array A are possible depending upon how numbers are removed from the sequence S.
Cost of array A is defined as S+S+.....+S[N-1]+S[N]. Where
S[i]=A[i]*(A[i-1]+1)*(A[i-2]+2) for 3<=i<=N
Now out of all possible permutations of A, Vinod wants to create array A in such a way that its cost is minimized. Help him find the least cost of array A out of all possible cases.
Input consists of single integer T representing numbers of games Vinod is going to play. Now for each game :
First line contains single integer N denoting size of sequence S.
Second line contains N integers denoting numbers in the sequence S.
For each game, print the least possible cost of array A in new line.
- 1 <=T<=25
- 1 <=N <=103
- 1 <=A[i] <=103
Input: 6 1 11 2 4 7 3 1 2 2 3 1 4 2 4 1 5 3 8 4 8 4 3 5 Output: 11 39 20 34 125 314
For test case 1, we select 11, so answer is 11.
For test case 2, we can select [4,7] or [7,4], and both will give 4+7*(4+1)=7+4*(7+1)=39.
For test case 3, if we select in order [2,2,1], we get 2+2*(2+1)+1*(2+1)*(2+2)=20.
For test case 4, we can select in order [2,4,1], and we get 2+4*(2+1)+1*(4+1)*(2+2)=34.
For test case 5, selecting in order [8,3,1,5] will give least cost=125.
For test case 6, selecting in order [8,4,3,5] will give least cost=314.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions