| Submit | All submissions | Best solutions | Back to list |
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.
| 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 |
hide comments
|
||||||
|
2024-05-15 12:47:01
1) use KarmarkarKarp partition algorithm, you can get 11.796614 points. 2) use CKK algorithm to improve above results, optimize the DFS procedure (run in 5s), then you can get > 15.0 points Last edit: 2024-05-18 11:52:43 |
||||||
|
2020-12-03 01:53:56 Rafail Loizou
there is no test case with n <= 32 so do not even bother doing a brute force solution to get these cases. |
||||||
|
2017-11-24 17:08:47
my solution is running within time limits but has 0.0 points,got it by sorting in decreasing order Last edit: 2017-11-24 17:10:00 |
||||||
|
2016-07-23 12:26:22
I used the "Meet in the middle" Algorithm and got 14.96 Point in C++14. Last edit: 2016-07-23 12:26:52 |
||||||
|
2016-07-23 12:20:15
I got 11.12109 points for randomized algorithm, brute force, and dynamic programming with bitmasking... But 11.796614 points scorer is very many. How to get 11.796614 points? Update: I used meet-in-the-middle algorithm and I got 12.335943 points! Last edit: 2016-07-24 03:07:32 |
||||||
|
2016-05-28 08:25:49
Got 0.0081 using difference. Gotta do better... Last edit: 2016-05-28 08:32:19 |
||||||
|
2016-05-28 08:13:12
Output shows 2 and 3. 2 is the no of bags in his left hand. What does 3 denote? Edit: Its numbers on bag NOT no. of bags.... Silly me Last edit: 2016-05-28 08:30:15 |
||||||
|
2016-01-18 10:17:06
Greedy approach does no good.. Just 2.921161 with python .. :/ Still good enough to fetch me 0.2 points duh .. :P |
||||||
|
2015-10-02 19:25:48
Last edit: 2015-10-02 19:34:25 |
||||||
|
2015-09-30 21:20:24
Ladies and Gentlemen The above example is just a demonstration of response; it is definitely a poor response . You must print the contents of the items to be loaded by the left hand . The best answer for the example would be : 1 3 For 5 + 4 = 9 Right hand carry 8 Consider dividing the total weight if the division is not exact , the left hand should carry the most weight. |
||||||
RSS