oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

ballpacking Output Only

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

ballpacking.html

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)

Tags

Creative

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110081s32MBCustom

Attachments

Attachment Filesize Last Updated
4.in341.81KB30 Jun 2018, 16:33:53
7.in3.81MB30 Jun 2018, 16:33:53
6.in1.91MB30 Jun 2018, 16:33:53
3.in68.37KB30 Jun 2018, 16:33:53
8.in7.75MB30 Jun 2018, 16:33:53
1.in612B30 Jun 2018, 16:33:53
2.in6.3KB30 Jun 2018, 16:33:53
5.in756.11KB30 Jun 2018, 16:33:53

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.