Diamond Diggers

All submissions for this problem are available.
Han Solo and Chewbacca start a space journey to planet Naboo on the Millennium Falcon. During the journey they land at a mysterious planet with high gravity where they find n diamond stones scattered all around. All the stones are of same weight. Each stone has a value according to its purity which can be detected by a special device. They choose to divide the stones fairly among themselves in two halves so that they carry almost equal weights such that the difference between the value of two halves is as small as possible. If n is even, then sizes of two halves must be strictly n/2 and if n is odd, then size of one half must be (n1)/2 and size of the other half must be (n+1)/2. Given the value of stones, help them to divide the stones among themselves.
Input
First line consists of an integer n which denotes the number of stones.Second line consists of n space separated integers denoting the value of the stones.
Output
First line consists of the values of the stones assigned to Han Solo.Second line consists of the values of the stones assigned to Chewbacca.Assume that the set containing the first value in the input is always assigned to Han Solo.Also the values in the output sets must follow the same ordering as the input.
Constraints
The number of stones can range from 2 to 99.The values of the stones vary from 1 to 10^4.
Example
Input: 7 1 2 3 4 5 6 7 Output: 1 2 4 7 3 5 6
Explanation
These 7 values must be separated into 2 sets of sizes 3 and 4.In this case, it is possible to form two sets (1,2,4,7) & (3,5,6) of equal size.The set containing the first value (i.e.) 1 must be assigned to Han Solo and the elements of the output sets have the same order as the input.
Author:  partha278 
Tags  partha278 
Date Added:  16122015 
Time Limit:  0.01  0.1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 