1094 - Containers
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 35
Solved: 9
- Description
- At a container terminal, containers arrive from the hinterland, one by one, by rail, by road,
or by small ships. The containers are piled up as they arrive. Then the huge cargo ships
arrive, each one capable of carrying thousands of containers. The containers are loaded into
the ships that will bring them to far away shores. Or the other way round, containers are
brought in over sea, piled up, and transported to the hinterland one by one. Anyway, a huge
parking lot is needed, to store the containers waiting for further transportation.
Building the new container terminal at the mouth of the river was a good choice. But
there are disadvantages as well. The ground is very muddy, and building on firm ground
would have been substantially cheaper. It will be important to build the parking lot not
larger than necessary.
A container is 40 feet long and 8 feet wide. Containers are stacked, but a stack will be
at most five containers high. The stacks are organized in rows. Next to a container stack,
and between two container stacks (along the long side of the containers) a space of 2 feet
is needed for catching the containers. Next to a row of stacks, and between two stacks
(along the short side of the containers) a space of 4 feet is needed for the crane that lifts the
containers. All containers are placed in the same direction, as the cranes can not make turns
on the parking lot.
The parking lot should be rectangular. Given the required capacity of the parking lot,
what will be the best dimension for the parking lot? In the first place the area should be
minimal. The second condition is that the parking lot should be as square as possible.
Below you see a plan for a parking lot with a capacity of 8 stacks. Two rows of four
containers each turns out to be the best solution here, with a total area of 92 × 42 = 3864.
- Input
- On the first line one positive number: the number of testcases, at most 100. After that per
testcase:
• A single positive integer n (n 1012) on a single line: the required capacity (number
of containers) for the parking lot. - Output
- Per testcase:
• A single line, containing the length, width (length width) and area of the optimal
solution. The optimal solution has the least possible area, and if there are multiple
solutions having the same area, the difference length − width should be minimal.
Use the sample format. - sample input
-
6 1 15 22 29 36 43
- sample output
-
48 X 12 = 576 48 X 32 = 1536 52 X 48 = 2496 92 X 32 = 2944 92 X 42 = 3864 136 X 32 = 4352
- hint
- source
- The 2007 ACM Northwestern European Programming Contest