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 1014).

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 log10 (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 log10 ((5+8+4)/(|8+4-5|+1))= 0.327 points.


hide comments
robbiedee: 2015-09-03 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: 2015-07-24 09:08:40

Last edit: 2015-07-24 10:04:54
reggaeguitar: 2015-02-09 23:05:55

Last edit: 2015-02-13 18:50:31
Abhishek: 2014-12-26 16:23:31

Can't do better than 3.25 , using O(nlogn) , how to increase score ?
@Adrian any hints?

[reply by cyclops: Read literature and don't give up so easily. Also, it's best not to give or ask for hints in comments.]

Last edit: 2014-12-26 18:11:35
Rachit: 2014-12-17 14:12:14

Last edit: 2014-12-17 14:32:37
3qu@t!0n: 2013-11-08 21:05:23

i got 1.850891 . what does it means ??
is it point??

Hitman: 2012-12-26 22:47:28

Try this
http://en.wikipedia.org/wiki/Partition_problem

Pathan Salman Khan: 2012-03-24 16:30:28

If i output 3 2 instead of 2 3 for given case, is it fine?

Santiago Palacio: 2012-02-15 15:10:09

@SHUBHAM KANSAL: it is an example, it never says it's the most effective or the highest score.

SHUBHAM KANSAL: 2012-02-13 15:08:17

i dont understand the given test case....
if he carries the bags with weights 4 and 5 in same hand then the difference is just 1,
but here the difference is 7...?????


Added by:adrian
Date:2004-07-10
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET