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
__KIRA__:
2012-01-05 21:45:58
@Adrian plz.. luk into my ID 6301101. i see it as the optimal solution. still 4.844. points only why ?? |
|
Giovanni Botta:
2011-08-05 15:15:22
I implemented the exponential algorithm and submitted it just to see. I get 0 point and 0.11 sec in time. I don't understand why I get 0 point? I'm 100% sure my algorithm works (I tested it). Is it running out of time without telling me?
|
|
skeeve:
2011-04-19 17:07:12
@Aaditya, it didn't say that the solution there was optimal. It was just demonstrating what the score would be for that solution. |
|
dark passenger:
2011-03-23 17:45:45
i dont understand the given test case....
|
|
bgbraithwaite:
2010-12-29 19:11:30
I have taken indexing from 1 to 10000, but i am still getting WA.Any other suggestions.
|
|
abhijith reddy d:
2010-03-16 05:03:15
NOTE: Indexing begins from 1 .. otherwise you'll end up getting WA |
|
mike:
2009-12-08 14:53:39
Im a bit confused does it matter which items end up in johnny's left or is the scoring done by a few possible solution, because couldn't the same items be in either hand? |
|
Todor Markov:
2009-06-30 21:05:21
What does "Wrong answer" mean here? Isn't each answer correct in this task?
|
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 |