JOHNNY  Johnny Goes Shopping
Johnny visited his favourite supermarket to purchase as many sweets as he could afford. Since daddy had left his credit card at home untended, this was not really a problem. Once he had (barely) managed to push the trolley laden with chocolate bars past the cash desk, he began to wonder how to carry all the shopping home without breaking his back.
You must know that Johnny is a perfectly normal child, and has exactly 2 hands. Help him distribute his load between both hands so as to minimise the difference in load between both hands.
Input
The first line of input contains a single integer n<= 10000 denoting the number of sweet packets Johnny has bought. In each of the next n lines a single positive integer is given, describing the weight of the respective packet (the weight is an integer value never exceeding 10^{14}).
Output
In separate lines, output the numbers of the packets which Johnny should carry in his left hand. Assume packets are numbered in the input order from 1 to n.
Scoring
Your program shall receive log_{10} (s/(d+1)) points, where s is the total weight of all parcels, while d denotes the difference in weight between the load carried in Johnny's left and right hand.
Example
For the sample input:
3 5 8 4
a program outputting:
2 3
will score log_{10} ((5+8+4)/(8+45+1))= 0.327 points.
hide comments
rishabh_iet:
20171124 17:08:47
my solution is running within time limits but has 0.0 points,got it by sorting in decreasing order Last edit: 20171124 17:10:00 

e869120:
20160723 12:26:22
I used the "Meet in the middle" Algorithm and got 14.96 Point in C++14. Last edit: 20160723 12:26:52 

square1001:
20160723 12:20:15
I got 11.12109 points for randomized algorithm, brute force, and dynamic programming with bitmasking...


xinnix:
20160528 08:25:49
Got 0.0081 using difference. Gotta do better... Last edit: 20160528 08:32:19 

xinnix:
20160528 08:13:12
Output shows 2 and 3.


dwij28:
20160118 10:17:06
Greedy approach does no good.. Just 2.921161 with python .. :/ Still good enough to fetch me 0.2 points duh .. :P 

ramky1107:
20151002 19:25:48
Last edit: 20151002 19:34:25 

alexbandeira:
20150930 21:20:24
Ladies and Gentlemen


robbiedee:
20150903 15:43:10
@Todor you should only output the number of each item from the input in the left hand  if you have added anything else like debug, or timings, you will get Wrong Answer. But yes, there are many such answers. 

vikram bhat:
20150724 09:08:40
Last edit: 20150724 10:04:54 
Added by:  adrian 
Date:  20040710 
Time limit:  5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 