Problem Description
Mr. Panda loves balls, especially symmetrical spherical balls. One day, Mr. Panda is moving house and he cannot bear to leave his balls behind and thus wants to transport all of them in perfectly shaped cylindrical shaped containers. These containers have a maximum base radius of Rmax metres as if the radius is too big the containers are too difficult to transport.
He has a set of N spherical balls of radii between L metres and U metres inclusive. He has decided to make a single cylinder container to transport these balls. When packing the balls, he will first place the cylindrical container on the ground with one of the circular sides lying flat on the ground. The other circular side will be opened and he will place the balls one by one into the container. Each ball he places will fall to the position that is closest to the ground due to gravity, except the first ball which will fall all the way and rest in a position that is touching the wall of the container. The container and balls are stiff and will not deform. The balls will rest on one another or against the wall of the container.
There are many ways to pack the balls and many possible radii of the cylinder he can choose from. Mr. Panda wants to pack the balls in such a way to maximise the volume efficiency of the packing. We define the volume efficiency of a packing to be (Total volume of the packed spheres)/(Volume of the container). Can you help him determine the combination of container radius and order of packing to get as high a volume efficiency as possible?
Input
This problem is an output only problem. You will be provided with 8 inputs. The first line of each input file contains 3 integers, N, Rmax and the score for that subtask S. The next N lines contain one integer each. The integer on the i-th line represents the radius of the i-th ball in micrometres. It is guaranteed that no matter what order you pack the balls, each ball will fall into a unique position that is closest to the ground.
Output
For each input, you are to submit an output file containing N+1 integers. The first integer contains the radius of the container you have chosen, R. The radius of the containers can only be manufactured to the nearest micrometre so the radius only needs to be given to the nearest micrometre. The next N integer should be a permutation of the integers {1,2,...,N}. The integers represent the order that the balls are packed with the first integer representing the index of the first ball that is packed and so on.
Scoring
Each input is worth a specific number of points as shown below.
| Input |
N |
L |
U |
Rmax |
Score |
| 1.in |
100 |
1024 |
1729 |
1936 |
4 |
| 2.in |
1000 |
7268 |
12048 |
13512 |
6 |
| 3.in |
10000 |
21924 |
32768 |
40762 |
8 |
| 4.in |
50000 |
53746 |
79043 |
90210 |
10 |
| 5.in |
100000 |
86400 |
138876 |
168249 |
13 |
| 6.in |
250000 |
123456 |
174975 |
204768 |
16 |
| 7.in |
500000 |
365364 |
598786 |
713594 |
19 |
| 8.in |
1000000 |
654321 |
1048576 |
1234567 |
24 |
For each subtask, your score will be as follows where Eans is the problem author's packing efficiency, E is your packing efficiency:
- If E ≥ Eans, the subtask will receive S points.
- If the output is invalid, the subtask will receive 0 points.
- For all other valid outputs, the score is calculated by floor(S*eN(E-Eans)/Eans)